FF's Roam Notes

Max Heap

5 min read

Algorithm

堆算法分别两类，最大堆算法和最小堆算法。 这里只说最大堆算法，最小堆同理。

最大堆需要满足两个条件：

  • 每个父亲节点的值需要大于或者等于其子节点的值。
  • 堆是一个完整二叉树

根据最大堆的生成条件，可以知道最大堆有如下性质：

  • 编号大于 的元素都没有子节点
  • 父亲节点 和子节点 之间满足固定的关系
  • 可以确保顶点元素最大

因此，我们考虑使用数组表示最大堆。将堆中元素从上到下，从左到右的填入数组中， 根据最大堆的性质，可以从堆顶元素索引到堆中所有元素。

插入元素

如何将一个元素插入已有最大堆中？

先放到数组最后，然后和父亲节点相比，如果大就交换，否则结束。

删除最大元素

如何在删除最大元素之后仍然可以保持最大堆的性质？

将最后一个元素和堆顶元素交换，然后对第一个元素做下沉操作，即和子节点比较，如果小则和子节点交换，否则结束。

构造最大堆

如何用已有数组构建一个最大堆？

  1. 在不考虑空间复杂度的情况下，使用新数组将数据一个一个插入即可。
  2. 原地构造，即不使用其他空间，原地构造最大堆。 可以从 开始向上（堆顶元素），对每个有子节点的元素做下沉处理。

堆排序

如何使用最大堆对数组进行排序？

  1. 构造最大堆。
  2. 取出最大堆的堆顶元素作为最大值，将堆中最后一个元素和堆顶元素交换，对堆顶元素做下沉处理。
  3. 循环第二步直到取出所有元素。

Implements

class MaxHeap:
    def __init__(self):
        self.nums = []
 
    def father(self, pos: int):
        """Find `pos` element's father element's pos."""
        return math.floor((pos - 1) / 2)
 
    def left_child(self, pos: int):
        """Find `pos` element's left child element's pos."""
        return (pos + 1) * 2 - 1
 
    def right_child(self, pos: int):
        """Find `pos` element's right child element's pos."""
        return (pos + 1) * 2
 
    def insert(self, num: int):
        """Insert `num` to max heap."""
        self.nums.append(num)
        p = len(self.nums)
        while num > self.nums[self.father(p)]:
            self.nums[p] = self.nums[self.father(p)]
            self.nums[self.father(p)] = num
            p = self.father(p)
 
    def pop(self):
        """Pop max element of the max heap."""
        num = self.nums[0]
        self.nums[0] = self.nums[-1]
        self.down(0)
 
    def down(self, pos: int, last_pos=None):
        """Sink `pos` element down to the right place."""
        if not last_pos:
            last_pos = len(self.nums)
        def find_max_pos(pos: int):
            left, right = self.left_child(pos), self.right_child(pos)
            if left < last_pos and right < last_pos:
                max_pos = left if self.nums[left] > self.nums[right] else right
            elif left < last_pos:
                max_pos = left
            elif right < last_pos:
                max_pos = right
            else:
                max_pos = pos
            return max_pos
        max_pos = find_max_pos(pos)
        while self.nums[pos] < self.nums[max_pos]:
            t = self.nums[pos]
            self.nums[pos] = self.nums[max_pos]
            self.nums[max_pos] = t
            pos = max_pos
            max_pos = find_max_pos(pos)
 
    def sort(self):
        # after sort, not a max heap anymore
        def swap(pos_a, pos_b):
            t = self.nums[pos_a]
            self.nums[pos_a] = self.nums[pos_b]
            self.nums[pos_b] = t
 
        p = len(self.nums) - 1
        while p > 0:
            swap(0, p)
            self.down(0, p)
            p -= 1
 
 
    def __str__(self):
        return str(self.nums)
 
 
def construct_max_heap(nums: List[int]):
    max_heap = MaxHeap()
    for n in nums:
        max_heap.insert(n)
    return max_heap
 
 
def construct_max_heap_inplace(nums: List[int]):
    max_heap = MaxHeap()
    max_heap.nums = nums
    for i in range(len(nums) // 2 - 1, -1, -1):
        max_heap.down(i)
    return max_heap

应用

Question?

构造最大堆时，为什么要从 开始向上（堆顶）进行下沉，而不是从堆顶向下？

只有在除堆顶之外节点都满足最大堆性质时，从能成功进行下沉操作。

Graph View