题目分析

堆是一种非常常见的数据结构，使用的频率也非常的高，小伙伴们经常使用堆，但是往往不关注其实现过程，今天给小伙伴们梳理一下堆的实现过程。

递归

堆是一个完全二叉树，可以通过数组进行实现，数组的下标对应节点的编号。设根节点的下标从0开始，那么它的左孩子和右孩子的编号为1和2，我们可以得出一个规律，下标为i的节点，它的左孩子和右孩子的编号为i x 2 + 1和i x 2 + 2。

我们以一个最小堆为例子，插入元素，要想获得最快的时间复杂度，因此我们要从尾部进行插入，让它和它的父节点进行比较，如果插入的元素更小，则需要和父节点进行交换，并且递归寻找它的爷爷节点进行比较。

删除元素时，要想获得最快的时间复杂度，因此我们要从尾部进行删除，因为要删除的元素在0号索引，因此要先交换头部元素和尾部元素的值，然后将尾部元素弹出。这时头部元素可能并不是最小的元素，因此要将它和它的左右孩子进行对比，哪一个小则和哪一个进行交换，并且递归寻找它的孙子节点进行比较。

计算长度和获取堆顶元素就非常简单了，长度就是数组的长度，堆顶元素就是数组的第一个元素。

class heap:
    @staticmethod
    def length(nums):
        return len(nums)
    
    @staticmethod
    def top(nums):
        return nums[0]
    
    @staticmethod
    def push(nums, x):
        nums.append(x)
        idx = len(nums) - 1
        while idx != 0:
            parent_idx = idx // 2
            if nums[idx] < nums[parent_idx]:
                nums[idx], nums[parent_idx] = nums[parent_idx], nums[idx]
                idx = parent_idx
            else:
                break

    @staticmethod
    def pop(nums):
        nums[0], nums[-1] = nums[-1], nums[0]
        res = nums.pop()
        lens, idx = len(nums), 0
        while True:
            temp = idx
            left = idx * 2 + 1
            right = idx * 2 + 2
            if left < lens and nums[idx] > nums[left]:
                idx = left
            if right < lens and nums[idx] > nums[right]:
                idx = right
            if idx == temp:
                break
            else:
                nums[idx], nums[temp] = nums[temp], nums[idx]
        return res


# 下面我使用自己创建的堆进行排序，验证正确性。
if __name__ == '__main__':

    a = [-4, 0, 7, 4, 9, -5, 1, 0, -7, -1]
    res = []

    for x in a:
        heap.push(res, x)

    a.clear()
    
    while res:
        a.append(heap.pop(res))

    print(a)

刷题总结

在数据结构和算法中，往往关注链表，栈，队列，树这些基本的数据结构，对于堆是小伙伴们容易遗忘的，请不要忘记它。