数据结构-堆(Heap) Python实现

堆（Heap）可以看成近似完全二叉树的数组，树中每个节点对应数组中一个元素。除了最底层之外，该树是完全充满的，最底层是从左到右填充的。

堆包括最大堆和最小堆：最大堆的每一个节点（除了根结点）的值不大于其父节点；最小堆的每一个节点（除了根结点）的值不小于其父节点。

本文以最大堆为例，先直观感受一下堆的样子：
图片来源

最大堆

观察上图不难发现，对于一个给定节点的下标i，其父节点、左孩子、右孩子的下标为：
parent(i): (i + 1) // 2 - 1
left(i): i * 2 + 1
right(i): i * 2 + 2
其中“//”表示除法后只取整数部分。

对于一个给定的数组，如何转化为堆呢？
对于一个任意节点，如果该节点大于左孩子和右孩子，则该节点无需移动。否则，和左右孩子中较大的那个交换位置，于是该节点满足大于左右孩子了，但是刚被交换了的孩子节点需要继续比较它的左右孩子......整个过程递归进行下去，我们可以轻松计算出：对于根节点，在进行转化成堆的过程中，最多需要交换h次（h为树的高度），对于树种的每个节点，如果都进行此操作，则整个过程的时间复杂度为：O(nlogn)。（n为节点数，logn≈h）
代码如下：

    def heapify(self):
        for i in range((len(self.heap) + 1) // 2 - 1, -1, -1):
            self.max_heapify_top(i)

    def max_heapify_top(self, i):
        """
        从上到下
        O(logn)
        """
        left = i * 2 + 1
        right = i * 2 + 2
        if left < len(self.heap) and self.heap[left] > self.heap[i]:
            largest = left
        else:
            largest = i
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            self.heap[largest], self.heap[i] = self.heap[i], self.heap[largest]
            self.max_heapify_top(largest)

以上代码中heapify函数从(len(self.heap) + 1) // 2 - 1到0进行遍历，是因为树中的叶子节点没有孩子，因此可以看成满足堆的性质，所以无需进行heapify，所以从非叶子节点开始遍历，节约时间。

如何从堆中弹出和插入元素呢？
先说弹出。由于是最大堆，因此每次弹出需要弹出最大的元素，那就是根节点，如何弹出后还保持堆的性质呢。具体做法是：先将树中根节点和最后一个节点交换位置，对应数组中就是第一个元素和最后一个元素交换位置，然后弹出最后一个元素，在对交换位置后的根节点进行heapify，这样弹出了最大元素，同时也保持了堆的性质。
代码如下：

    def pop(self):
        """
        O(logn)
        """
        self.heap[0], self.heap[len(self.heap) - 1] = self.heap[len(self.heap) - 1], self.heap[0]
        value = self.heap.pop()
        self.max_heapify_top(0)
        return value

插入元素。
先将元素放在树的末尾，也是数组的末尾，再按照自下而上的顺序依次比较与父节点的大小关系，自下而上进行heapify。
代码如下：

    def push(self, value):
        """
        O(logn)
        """
        self.heap.append(value)
        self.max_heapify_button(len(self.heap) - 1)

    def max_heapify_button(self, i):
        """
        从下到上
        O(logn)
        """
        parent = (i + 1) // 2 - 1
        if parent >= 0 and self.heap[parent] < self.heap[i]:
            smallest = parent
        else:
            smallest = i

        if smallest != i:
            self.heap[smallest], self.heap[i] = self.heap[i], self.heap[smallest]
            self.max_heapify_button(smallest)

整个堆的实现代码为：

class Heap:

    def __init__(self, heap=[]):
        self.heap = heap

    def heapify(self):
        for i in range((len(self.heap) + 1) // 2 - 1, -1, -1):
            self.max_heapify_top(i)

    def max_heapify_top(self, i):
        """
        从上到下
        O(logn)
        """
        left = i * 2 + 1
        right = i * 2 + 2
        if left < len(self.heap) and self.heap[left] > self.heap[i]:
            largest = left
        else:
            largest = i
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            self.heap[largest], self.heap[i] = self.heap[i], self.heap[largest]
            self.max_heapify_top(largest)

    def max_heapify_button(self, i):
        """
        从下到上
        O(logn)
        """
        parent = (i + 1) // 2 - 1
        if parent >= 0 and self.heap[parent] < self.heap[i]:
            smallest = parent
        else:
            smallest = i

        if smallest != i:
            self.heap[smallest], self.heap[i] = self.heap[i], self.heap[smallest]
            self.max_heapify_button(smallest)

    def pop(self):
        """
        O(logn)
        """
        self.heap[0], self.heap[len(self.heap) - 1] = self.heap[len(self.heap) - 1], self.heap[0]
        value = self.heap.pop()
        self.max_heapify_top(0)
        return value

    def push(self, value):
        """
        O(logn)
        """
        self.heap.append(value)
        self.max_heapify_button(len(self.heap) - 1)

再说堆排序呢？对于一个任意的数组，进行构建堆之后，再按照顺序依次弹出堆中的元素，便得到了有序的数组。更神奇的是，在数组末尾添加一个指针，便可实现数组的原地排序（不需要额外空间）。堆排序的时间复杂度为：O(nlogn)，空间复杂度为：O(1)