Python优先级队列Heapify方法

Question

我将此库用于堆：

from Queue import PriorityQueue

我需要触发heapify，因为在此优先级队列中我插入了一个节点类，并且优先级队列是基于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 nodes值，例如：

first.val = 100

有没有像pq.heapify（）之类的方法

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

Answer 1

我认为最好使用heapq library作为堆

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

优势：

1. 该方法允许使用replace更新最小的元素
2. 只需O（log（n））即可更新最小元素的值（即首先从1更改为100）
3. 当只需要更新一个项目时（需要O（n））比使用Heapify更快

代码

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