Python PriorityQueue Heapify 方法

Question

我正在将这个库用于堆：

from Queue import PriorityQueue

我需要触发 heapify，因为在这个优先级队列中我插入了一个节点 class 并且优先级队列是基于 node.val 排序的，如下所示：

class Node():
   __init__(self,val,text):
       self.val = val
       self.text = text

和我的 pq：

pq = PriorityQueue()
first = Node(1,'abcd')
pq.put((first.val,first))

xyz = Node(10,'asdf')
pq.put((xyz.val,xyz))


fsa = Node(7,'asdsbcd')
pq.put((fsa.val,fsa))

现在它工作正常，但如果我想像这样更改第一个节点值：

first.val = 100

有没有像pq.heapify()之类的方法..

如何调用 heapify 方法以便它可以对其进行排序？因为如果我不这样做，那么它将对列表进行排序并假设第一个仍然是 1 而不是 100。

Answer 1

我相信你的堆使用 heapq library 会更好。

然后您可以使用 this answer 中的进程来更新堆中的最小值，如下所示。

优点：

方法允许使用替换更新最小元素。
只需要 O(log(n)) 来更新最小元素的值（即首先从 1 变为 100）
当只需要更新一个项目时比使用 Heapify 更快（需要 O(n)）

代码

import heapq

class Node():
  def __init__(self,val,text):
       self.val = val 
       self.text = text
  def __str__(self):   # Add a method to node to string for display
    return f'{self.val}, {self.text}'

class MyHeap(object):
  """The class keeps an internal list, where each element is a tuple.
    The first tuple element is the priority (val), calculated at element insertion 
    time, using the key parameter, passed at Heap instantiation"""
  def __init__(self, initial=None, key=lambda x:x.val):
    self.key = key
    if initial:
      self._data = [(key(item), item) for item in initial]
      heapq.heapify(self._data)
    else:
      self._data = []

  def push(self, item):
    heapq.heappush(self._data, (self.key(item), item))

  def pop(self):
    return heapq.heappop(self._data)[1]

  def replace(self, item):
    # Pops min element and adds a new element
    v = self.pop()
    self.push(item)
    return v

测试

测试 1. 添加元素并转储堆

# Add elements
pq = MyHeap()
first = Node(1,'abcd')
pq.push(first)

xyz = Node(10,'asdf')
pq.push(xyz)

fsa = Node(7,'asdsbcd')
pq.push(fsa)

# Dump elements in order
print('Initial Ordering')
while pq._data:
  print(pq.pop())

结果

Initial Ordering
1, abcd
7, asdsbcd
10, asdf

测试 2. 删除最小值并添加为具有新值的较大值的新元素

# Add elements
pq.push(first)
pq.push(xyz)
pq.push(fsa)

# Update first element using replace
first.val = 100
pq.replace(first)

print('\nNew Ordering')
while pq._data:
  print(pq.pop())

结果

New Ordering
7, asdsbcd
10, asdf
100, abcd

测试 3：将元素添加为列表

print('\nUsing List')
pq = MyHeap([first, xyz, fsa])
while pq._data:
  print(pq.pop())

结果

Using List
7, asdsbcd
10, asdf
100, abcd

Python PriorityQueue Heapify 方法

Python PriorityQueue Heapify Method

python

heap

priority-queue