Python中的最小堆实现

import math class MinHeap: def __init__(self, arr): self.arr = arr self.n = len(arr) def heapify(self): depth = int(math.log2(self.n)) for i in range((2 ** depth) - 2, -1, -1): self.sift_down(i) def sift_down(self, i): while (2 * i) + 1 < self.n or (2 * i) + 2 < self.n: i = self.sift_down_level(i) def sift_down_level(self, i): left_smaller = right_smaller = False if self.is_left_child_exists(i) and self.arr[(2 * i) + 1] < self.arr[i]: left_smaller = True if self.is_right_child_exists(i) and self.arr[(2 * i) + 2] < self.arr[i]: right_smaller = True if left_smaller and right_smaller: if self.arr[(2 * i) + 1] < self.arr[(2 * i) + 2]: self.arr[(2 * i) + 1], self.arr[i] = self.arr[i], self.arr[(2 * i) + 1] return (2 * i) + 1 else: self.arr[(2 * i) + 2], self.arr[i] = self.arr[i], self.arr[(2 * i) + 2] return (2 * i) + 2 elif left_smaller: self.arr[(2 * i) + 1], self.arr[i] = self.arr[i], self.arr[(2 * i) + 1] return (2 * i) + 1 elif right_smaller: self.arr[(2 * i) + 2], self.arr[i] = self.arr[i], self.arr[(2 * i) + 2] return (2 * i) + 2 return -1 def is_left_child_exists(self, i): if (2 * i) + 1 < self.n: return True return False def is_right_child_exists(self, i): if (2 * i) + 2 < self.n: return True return False nums = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] heap = MinHeap(nums) heap.heapify()

您应该避免代码重复:只在一个地方执行交换。避免重新计算 2 * i + 1 好几次。是的,减少你检查的条件数量。只需检查两个子项(如果有两个)中哪一个值最小,然后进行比较那个使用父对象的值。就这样。

其他一些评论:

我不会将数组的长度存储在属性中,因为这样一来,每次从堆中推送或提取值时,都会有更新数组的开销。
不需要执行对数和幂运算。只需计算最后一个节点的父节点在哪里。最后一个节点位于索引处 len()-1 ,所以它的父母在 (len()-1-1)//2 这就是 len()//2-1 .
这个 while 状况 sift_down 不应该重复你将要做的检查 sift_down_level .只需验证返回值不是-1。
打电话 heapify 在初始化过程中

在不对您的设计进行其他更改的情况下,我们可以得到以下结果:

class MinHeap:
    def __init__(self, arr):
       self.arr = arr
       self.heapify()

    def heapify(self):
        for i in range(len(self.arr) // 2 - 1, -1, -1):
            self.sift_down(i)

    def sift_down(self, i):
        while i != -1:
            i = self.sift_down_level(i)

    def sift_down_level(self, i):
        child = i * 2 + 1
        if child < len(self.arr):
            if child + 1 < len(self.arr) and self.arr[child + 1] < self.arr[child]:
                child += 1
            if self.arr[child] < self.arr[i]:
                self.arr[child], self.arr[i] = self.arr[i], self.arr[child]
                return child
        return -1