实现 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函数已经错了。

你的堆的根元素存储在数组索引0中，子元素在1和2中。1的父元素是0，这是正确的，但2的父元素也应该是0，而你的函数returns1.

通常堆的底层数组不使用索引 0，而是根元素位于索引 1。这样您就可以像这样计算父项和子项：

parent(i): i // 2
left_child(i): 2 * i
right_child(i): 2 * i + 1

Answer 2

主要问题是parent函数错误。因为它应该与 left 和 right 方法相反，所以您应该先从 i 中减去 1，然后再将该值减半：

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

其他注意事项：

会员self.min_index你真的没有什么用处。它是 0 或 None，并且在您的代码中并没有真正使用差异，因为它直接来自堆是否为空。这也意味着您不需要 _find_min 方法（这本身很奇怪：您分配给 min，但从不使用它）。无论如何，删除那个方法，以及你调用它的那一行。还要删除将 None 分配给 self.min_index 的行，以及唯一读取值的其他地方，只需使用 0.
您有两种方法可以防止 min_heapify 方法中的索引错误：<= heapsize 和 try 块。第一个保护确实应该有<而不是<=，但是你应该只使用一种方式，而不是两种方式。所以要么测试小于，要么捕获异常。
带smallest = i的else块是不必要的，因为那时smallest == i.
min_heapify 有第一个参数，总是接收堆的完整大小。所以它是一个不必要的参数。使用另一个值调用此方法也没有意义。因此，从方法定义和所有调用中删除该参数。然后在该函数中将 heap_size = len(self.queue) 定义为本地名称
在 heap_decrease_key 中你注释掉了赋值 #self.queue[i] = key，只要你从不调用这个方法来真正 decrease 关键。但是，尽管您从未在 "inside" 和 class 中这样做，但 class 的用户很可能希望以这种方式使用它（因为这就是方法名称所暗示的）。所以最好取消注释该作业。
通过上述更改，您的实例将只有 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

实现 PriorityQueue 算法

Implementing a PriorityQueue Algorithm

algorithm

heap

data-structures