algorithm - 实现 PriorityQueue 算法

Question

这是我对 PriorityQueue 算法的实现。我有一种感觉，我的弹出功能是错误的。但我不确定到底哪里错了。我已经多次检查我的逻辑哪里出错了，但它似乎是完全正确的(用 CLRS 伪代码检查过)。

class PriorityQueue:
"""Array-based priority queue implementation."""
def __init__(self):
    """Initially empty priority queue."""
    self.queue = []
    self.min_index = None

def parent(self, i):
    return int(i/2)

def left(self, i):
    return 2*i+1

def right(self, i):
    return 2*i+2

def min_heapify(self, heap_size, i):
    #Min heapify as written in CLRS
    smallest = i
    l = self.left(i)
    r = self.right(i)
    #print([l,r,len(self.queue),heap_size])

    try:
        if l <= heap_size and self.queue[l] < self.queue[i]:
            smallest = l
        else:
            smallest = i
    except IndexError:
        pass
    try:
        if r <= heap_size and self.queue[r] < self.queue[smallest]:
            smallest = r

    except IndexError:
        pass

    if smallest != i:
        self.queue[i], self.queue[smallest] = self.queue[smallest], self.queue[i]
        self.min_heapify(heap_size, smallest)

def heap_decrease_key(self, i, key):
    #Implemented as specified in CLRS
    if key > self.queue[i]:
        raise ValueError("new key is larger than current key")

    #self.queue[i] = key

    while i > 0 and self.queue[self.parent(i)] > self.queue[i]:
        self.queue[i], self.queue[self.parent(i)] = self.queue[self.parent(i)], self.queue[i]
        i = self.parent(i)

def __len__(self):
    # Number of elements in the queue.
    return len(self.queue)

def append(self, key):
    """Inserts an element in the priority queue."""
    if key is None:
        raise ValueError('Cannot insert None in the queue')
    self.queue.append(key)
    heap_size = len(self.queue)
    self.heap_decrease_key(heap_size - 1, key)

def min(self):
    """The smallest element in the queue."""
    if len(self.queue) == 0:
        return None
    return self.queue[0]

def pop(self):
    """Removes the minimum element in the queue.

    Returns:
        The value of the removed element.
    """
    if len(self.queue) == 0:
        return None
    self._find_min()
    popped_key = self.queue[self.min_index]
    self.queue[0] = self.queue[len(self.queue)-1]
    del self.queue[-1]
    self.min_index = None
    self.min_heapify(len(self.queue), 0)
    return popped_key

def _find_min(self):
    # Computes the index of the minimum element in the queue.
    #
    # This method may crash if called when the queue is empty.
    if self.min_index is not None:
        return
    min = self.queue[0]
    self.min_index = 0

任何提示或输入将不胜感激

Answer 1

主要问题是 parent功能错误。因为它应该与 left 相反和 right方法，您应该先从 i 中减去 1在将该值减半之前:

def parent(self, i):
    return int((i-1)/2)

其他注意事项:

• 您对成员(member)self.min_index 没有什么用处| .它是 0 或 None ，并且您的代码中并未真正使用差异，因为它直接来自堆是否为空。这也意味着您不需要方法 _find_min , (这本身很奇怪:您分配给 min ，但从不使用它)。无论如何，删除那个方法，以及你调用它的那一行。同时删除分配 None 的行至 self.min_index ，以及您读取值的唯一其他地方，只需使用 0。

• 您有两种方法来防止 min_heapify 中的索引错误方法:<= heapsize和一个 try堵塞。第一次保护真的应该有<而不是 <= ，但您应该只使用一种方式，而不是两种方式。因此，要么测试小于号，要么或捕获异常。

• else用 smallest = i block 没必要，因为那时候smallest == i .

• min_heapify有第一个参数，总是接收堆的全部大小。所以它是一个不必要的参数。使用另一个值调用此方法也没有意义。因此，从方法定义和所有调用中删除该参数。然后定义heap_size = len(self.queue)作为该函数中的本地名称

• 在 heap_decrease_key你注释掉了作业 #self.queue[i] = key ，只要您从不调用此方法来真正减少一个键就可以了。但是，尽管您永远不会从类的“内部”执行此操作，但类的用户很可能希望以这种方式使用它(因为这就是方法名称所暗示的)。所以最好取消对该作业的注释。

• 通过上述更改，您的实例将只有 queue作为其数据属性。这很好，但你可以考虑让 PriorityQueue继承自 list ，这样您也不需要此属性，只需使用您继承的列表即可。因此，您应该替换 self.queue与 self在整个代码中，您可以删除 __init__和 __len__方法，自 list实现这些正是您所需要的。在你想调用 list 的情况下需要小心一点。原始方法，当你覆盖它时，比如 append .在那种情况下使用 super().append .

应用上述所有更改后:

class PriorityQueue(list):
    """Array-based priority queue implementation."""
    def parent(self, i):
        return int((i-1)/2)

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def min_heapify(self, i):
        #Min heapify as written in CLRS
        heap_size = len(self)
        smallest = i
        l = self.left(i)
        r = self.right(i)

        if l < heap_size and self[l] < self[i]:
            smallest = l
        if r < heap_size and self[r] < self[smallest]:
            smallest = r

        if smallest != i:
            self[i], self[smallest] = self[smallest], self[i]
            self.min_heapify(smallest)

    def heap_decrease_key(self, i, key):
        #Implemented as specified in CLRS
        if key > self[i]:
            raise ValueError("new key is larger than current key")

        self[i] = key

        while i > 0 and self[self.parent(i)] > self[i]:
            self[i], self[self.parent(i)] = self[self.parent(i)], self[i]
            i = self.parent(i)

    def append(self, key):
        """Inserts an element in the priority queue."""
        if key is None:
            raise ValueError('Cannot insert None in the queue')
        super().append(key)
        heap_size = len(self)
        self.heap_decrease_key(heap_size - 1, key)

    def min(self):
        """The smallest element in the queue."""
        if len(self) == 0:
            return None
        return self[0]

    def pop(self):
        """Removes the minimum element in the queue.

        Returns:
            The value of the removed element.
        """
        if len(self) == 0:
            return None
        popped_key = self[0]
        self[0] = self[-1]
        del self[-1]
        self.min_heapify(0)
        return popped_key