如何初始化最小堆？

Question

我正在尝试弄清楚如何使用数组初始化最小堆。到目前为止，我的函数如下所示：

    def start_heap(self,n):
        # None positions to be filled with Nodes
        arr = [none][] * n
        for i in arr:
            heapify(i) 

    def heapify(self):
        start = self.parent(len(self) - 1) # Start at parent of last leaf
        for j in range(start, -1, -1):      # going to and including the root.
            self.heapify_down(j)

 def heapify_down(self, i):
        n = len(self._pq)
        left, right = self.left(i), self.right(i)
        if left < n:
            child = left
            if right < n and self.pq[right] < self.pq[left]:
                child = right
            if self.pq[child] < self.pq[i]:
                self.swap(i, child)
                self.heapify_down(child)

Heapify 伪代码：

Heapify-down(H,i): Let n = length(H) If 2i>n then
Terminate with H unchanged Else if 2i<n then
Let left=2i, and right=2i+1
Let j be the index that minimizes key[H[left]] and key[H[right]] Else if 2i=n then
Let j=2i Endif
If key[H[j]] < key[H[i]] then
swap the array entries H[i] and H[j] Heapify-down(H , j)
Endif

我将构建一个只保存数据的简单节点 class，但我不确定如何真正让 start_heap 函数正常工作。请记住 n 是可以存储的最大元素数。

Answer 1

对您提供的代码（不是您未提供的代码）的一些评论：

arr 是一个局部变量，所以无论你用它做什么，一旦函数 returns，那个 arr 就会超出范围......和丢失。您需要一个属性或子类 list
“分配”数组并用 None 填充它不是常见的做法。 Python 中的列表是动态的，因此您无需提前保留位置。您只需要一个空列表即可开始。
堆为空时不需要调用heapify
肯定没必要在循环中多次调用heapify。堆化的所有逻辑都已经存在于该方法中，因此无需在每个索引上单独调用它。但正如前一点所述：无需在空列表上调用它——没有任何可移动的东西。

所以更正是非常基本的：

    def start_heap(self, max_size):
        self.max_size = max_size
        self._pq = []

然后，在您的许多其他方法中，您将不得不使用 self._pq 和 self.max_size。

例如，它可以有一个指示堆是否已满的方法：

    def is_full(self):
        return len(self._pq) >= self.max_size

如果你有一个add方法，它会首先检查是否还有空间：

   def add(self, node):
       if is_full(self):
           raise ValueError("Cannot add value to the heap: it is full")
       # ... rest of your code ...

如何初始化最小堆？

How to Initialize a Min Heap?

python

arrays

queue

priority-queue

heap