如何使用Queue.PriorityQueue作为maxheap python

vc9ivgsu  于 2023-08-08  发布在  Python
关注(0)|答案(5)|浏览(93)

如何使用Queue.PriorityQueue作为maxheap python?
PriorityQueue的默认实现是minheap,在文档中也没有提到它是否可以用于maxheap。
有人能告诉我们是否可以使用Queue.PriorityQueue作为maxheap

db2dz4w8

db2dz4w81#

PriorityQueue默认只支持minheaps。
用它实现max_heaps的一种方法可能是,

# 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())

字符串

qyzbxkaa

qyzbxkaa2#

是的,有可能。
假设你有一个列表:

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

字符串
现在,假设您希望首先打印出max元素(或任何其他具有最大优先级的元素)。然后逻辑是通过将优先级乘以-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]


注:Python中的库是queue.PriorityQueue

ttvkxqim

ttvkxqim3#

根据注解,获取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())

字符串

moiiocjp

moiiocjp4#

反转键的值并使用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

字符串

s3fp2yjn

s3fp2yjn5#

@Kusharga在上面有一个优雅的回答。为了遵守优先级队列中元素的(priority,value)结构, Package 器类可以修改如下:

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}"

字符串

相关问题