Python:在优先级队列实现中使用我的堆

Question

我在使用要在Priority Queue类中使用的定制堆类函数时遇到了真正的问题。我在堆类中的哪些函数用于PriorityQueue的"enqueue"、"dequeue"、"front"one_answers"size"函数时遇到了问题。我知道对于"入队"，我需要使用插入函数，但我不知道如何进行，因为我有优先权。有人能帮我做些什么，让我的PriorityQueue类使用Heap类中的函数，以便正常工作吗？我已经被这个问题困扰了一段时间，我一直在寻找答案，包括使用内置的python函数，如queue和heapq。

类堆(对象):

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 the 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 the right child, determine the 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 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 the item down.
self.heap[position] = self.heap[parent]
position = parent
parent = position // 2
# Puts the new item in the 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

所以这是有效的，但正如我之前所说的，我在如何从中获得优先队列方面遇到了麻烦？我知道索要代码是错误的，但我很绝望，有人能帮我吗？我有我想让我的优先代码做什么的基本概要。

#PriorityQueue.py
from MyHeap import Heap

class PriorityQueue(object):
def __init__(self):
self.heap = None
def enqueue(self, item, priority):
'''Post: Item is inserted with specified priority in the PQ.'''
self.heap.insert((priority, item))
def first(self):
'''Post: Returns but does not remove the highest priority item from the PQ.'''
return self.heap[0]
def dequeue(self):
'''Post: Removes and returns the highest priority item from the PQ.'''
if self.heap is None:
raise ValueError("This queue is empty.")
self.heap.delete_max()
def size(self):
'''Post: Returns the number of items in the PQ.'''
return self.size

这是我到目前为止得到的，但我不知道这是否完全正确。有人能帮我吗？

我将代码编辑为最新版本。

Answer 1

由于这大概是家庭作业，所以我所能做的就是给出提示，这通常更容易作为注释来完成。由于这是一系列相当彻底的提示，我在这里总结它们作为答案。

在大多数情况下，PriorityQueue类中的方法将映射到Heap类中已经实现的方法：

• PriorityQueue.enqueue()很容易映射到Heap.insert()
• PriorityQueue.first()没有相应的堆方法，但仍然可以在一行中实现。您只需要返回最大值，该值将始终位于堆中的特定位置
• PriorityQueue.dequeue()稍微复杂一些。它需要先保存顶部项的值，以便在调用heap.delete_max()后返回
• 堆类已经有一个size()方法，PriorityQueue.size()可以调用该方法，而不是在PriorityQueue类中维护一个单独的大小变量

此外，您需要一个init函数，它应该创建一个新的Heap对象，该对象将由类维护。

为了制作迭代器，您需要制作一个新的类。它需要维护一个整数变量(让我们称之为self.index)，指示它在队列中的当前位置。您还需要一个增加self.index并返回上一个索引位置的值的方法。应该就是这样。