如何在Python中使用Queue.PriorityQueue作为最大堆

Question

如何将Queue.PriorityQueue用作Python中的最大堆？

Queue.PriorityQueue的默认实现是最小堆，文档中也没有提到是否可以将其用于最大堆。

请问有人能告诉我是否可以将Queue.PriorityQueue用作最大堆吗？

- Prashant Bhanarkar

---

请尝试阅读此链接：https://dev59.com/LHE95IYBdhLWcg3wApHk - minji

@Minji 在提到的链接中没有堆推函数。 - Prashant Bhanarkar

一个简单的方法是反转优先级。也就是说，如果你的项目优先级为2，将其改为-2。 - Jim Mischel

Answer 1

PriorityQueue默认只支持minheap。

实现max_heap的一种方法是：

# Max Heap
class MaxHeapElement(object):

    def __init__(self, x):
        self.x = x

    def __lt__(self, other):
        return self.x > other.x

    def __str__(self):
        return str(self.x)


max_heap = PriorityQueue()

max_heap.put(MaxHeapElement(10))
max_heap.put(MaxHeapElement(20))
max_heap.put(MaxHeapElement(15))
max_heap.put(MaxHeapElement(12))
max_heap.put(MaxHeapElement(27))

while not max_heap.empty():
    print(max_heap.get())

- Kushagra Verma

Answer 2

是的，这是可能的。

假设你有一个列表：

k = [3,2,6,4,9]

现在，假设您想首先打印出最大的元素（或任何具有最大优先级的其他元素）。那么逻辑是通过将其乘以-1来反转优先级，然后使用支持最小优先队列的PriorityQueue类对象将其变为最大优先队列。

例如：

k = [3,2,6,4,9]
q = PriorityQueue()
for idx in range(len(k)):
    # We are putting a tuple to queue - (priority, value)
    q.put((-1*k[idx], idx))

# To print the max priority element, just call the get()
# get() will return tuple, so you need to extract the 2nd element
print(q.get()[1]

注意：Python3中的queue.PriorityQueue是一个库。

- srth12

Answer 3

根据评论，获取maxHeap的最简单方法是插入元素的负数。

max_heap = PriorityQueue()

max_heap.put(MaxHeapElement(-10))
max_heap.put(MaxHeapElement(-20))
max_heap.put(MaxHeapElement(-15))
max_heap.put(MaxHeapElement(-12))
max_heap.put(MaxHeapElement(-27))

while not max_heap.empty():
    print(-1*max_heap.get())

- Vaibhav Desai

Answer 4

反转键的值并使用heapq。例如，将1000.0转换为-1000.0，将5.0转换为-5.0。

from heapq import heappop, heappush, heapify

heap = []
heapify(heap)

heappush(heap, -1 * 1000)
heappush(heap, -1 * 5)
-heappop(heap) # return 1000
-heappop(heap) # return 5

- Pay C.

Answer 5

@ Kusharga 在上面给出了一个优雅的答案。为了遵循优先级队列中元素的（优先级、值）结构，可以对包装类进行以下修改：

class MaxHeapElement(object):

   def __init__(self, priority, value):
       self.priority = priority
       self.value = value

   def __lt__(self, other):
       return self.priority > other.priority

   def __str__(self):
       return f"{self.priority}, {self.value}"

- pakpe