我正在使用 Python 中的最大堆数据结构实现优先级队列。我使用了几个名称，它们的优先级是与其关联的数字（9 是最高的，1 是最低的）。我面临的问题是，当我从优先级队列中出列一个项目时，它不会使具有最高优先级的项目出列。我认为这意味着我的队列存在问题，并且它没有根据项目的优先级将项目插入堆中的正确位置。如果有人能帮我解决这个问题，将不胜感激。
我的优先队列代码：
from Heap import Heap
class priorityQ(object):
def __init__(self):
self.PQ = Heap()
def enqueue(self, priority, item):
self.PQ.insert((priority, item))
def dequeue(self):
if self.PQ.size() == 0:
raise ValueError("Empty Queue")
return self.PQ.delete_max()
def first(self):
return self.PQ.get_max()
def size(self):
return self.PQ.size()
def main():
myHeap = priorityQ()
print(myHeap.size())
myHeap.enqueue(8, "Kaneda")
myHeap.enqueue(6, "Masaru")
myHeap.enqueue(9, "Akira")
myHeap.enqueue(4, " Kei")
myHeap.enqueue(5, "Takashi")
myHeap.enqueue(2, "Shikishima")
myHeap.enqueue(3, "Kiyoko")
myHeap.enqueue(1, "Yamagata")
myHeap.enqueue(7, "Tetsuo")
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
运行代码并调用 main 后的输出：
0
(9, 'Akira')
9
(7, 'Tetsuo')
8
(5, 'Takashi')
7
(4, 'Kei')
6
(3, 'Kiyoko')
5
(2, 'Shikishima')
4
(1, 'Yamagata')
3
(1, 'Yamagata')
2
(1, 'Yamagata')
1
None
0
最大堆代码（教科书提供）：
# Heap.py
class Heap(object):
#------------------------------------------------------------
def __init__(self, items=None):
'''post: a heap is created with specified items'''
self.heap = [None]
if items is None:
self.heap_size = 0
else:
self.heap += items
self.heap_size = len(items)
self._build_heap()
#------------------------------------------------------------
def size(self):
'''post: returns number of items in the heap'''
return self.heap_size
#------------------------------------------------------------
def _heapify(self, position):
'''pre: items from 0 to position - 1 satisfy the heap property
post: heap property is satisfied for the entire heap'''
item = self.heap[position]
while position * 2 <= self.heap_size:
child = position * 2
# if right child, determine maximum of two children
if (child != self.heap_size and
self.heap[child+1] > self.heap[child]):
child += 1
if self.heap[child] > item:
self.heap[position] = self.heap[child]
position = child
else:
break
self.heap[position] = item
#------------------------------------------------------------
def delete_max(self):
'''pre: heap property is satisfied
post: maximum element in heap is removed and returned'''
if self.heap_size > 0:
max_item = self.heap[1]
self.heap[1] = self.heap[self.heap_size]
self.heap_size -= 1
self.heap.pop()
if self.heap_size > 0:
self._heapify(1)
return max_item
def get_max(self):
if self.heap_size > 0:
max_item = self.heap[1]
self.heap[1] = self.heap[self.heap_size]
if self.heap_size > 0:
self._heapify(1)
return max_item
#------------------------------------------------------------
def insert(self, item):
'''pre: heap property is satisfied
post: item is inserted in proper location in heap'''
self.heap_size += 1
# extend the length of the list
self.heap.append(None)
position = self.heap_size
parent = position // 2
while parent > 0 and self.heap[parent] < item:
# move item down
self.heap[position] = self.heap[parent]
position = parent
parent = position // 2
# put new item in correct spot
self.heap[position] = item
#------------------------------------------------------------
def _build_heap(self):
'''pre: self.heap has values in 1 to self.heap_size
post: heap property is satisfied for entire heap'''
# 1 through self.heap_size
for i in range(self.heap_size // 2, 0, -1): # stops at 1
self._heapify(i)
#------------------------------------------------------------
def heapsort(self):
'''pre: heap property is satisfied
post: items are sorted in self.heap[1:self.sorted_size]'''
sorted_size = self.heap_size
for i in range(0, sorted_size - 1):
# Since delete_max calls pop to remove an item, we need
# to append a dummy value to avoid an illegal index.
self.heap.append(None)
item = self.delete_max()
self.heap[sorted_size - i] = item