定义

最大/小堆是一种特殊的树结构，本质上是一个完全二叉树，且满足 1）堆树中某个节点的值总是不大于或不小于其孩子节点的值 2）堆树中的每个节点的子树都是堆树

除了最后一层有缺失外，其他是满的，且最后一层缺失的叶子节点只出现在右侧，这样的二叉树叫完全二叉树 图1.1

这里以最大堆为例，我们通过层序遍历的方式，将二叉树节点存储在数组中。

任意一个最大堆满足这样的性质：

  1. index = 0 是根节点
  2. 对于非叶节点index，左孩子为: $2 * index + 1$ , 右孩子为: $2 * index + 2$
  3. 对于任意非根节点index，其父节点为: $(index - 1) / 2 $

下图是一个最大堆例子，图源wikipedia 图1.2

对于最大堆来说，常见的基本操作有：创建、插入、删除这三种。

public struct Heap<T: Comparable> {
    func buildMaxHeap(_ array: inout [T])
    func insert(_ value: T)
    func pop() -> T?
}

插入操作

最大堆的插入可以看成是“节点上浮（siftUp）”，每次插入都是先将节点添加到最后一个叶子节点的位置，然后逐步向上移动比较，直到到达满足最大堆要求的位置。（任意父亲节点值比孩子节点大） 时间复杂度：$O(logn)$，因为每次向上调整最多涉及树的高度，而完全二叉树的高度是$O(logn)$。

swift实现代码如下：

    public mutating func insert(_ value: T) {
        heap.append(value)
        siftUp(from: heap.count - 1)
    }
    
    private mutating func siftUp(from index: Int) {
        var childIndex = index
        let childValue = heap[childIndex]
        var parentIndex = self.parentIndex(of: childIndex)
         while childIndex > 0 && childValue > heap[parentIndex] {
             heap[childIndex] = heap[parentIndex]
             childIndex = parentIndex
             parentIndex = self.parentIndex(of: childIndex)
         }
        heap[childIndex] = childValue
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }

这是一个上浮操作示意图：

删除操作

最大堆的删除操作，就是从堆的根节点删除元素。然后保证根元素被删之后剩下的树节点依然能保持最大堆。

然后这里的一般操作是把最后一个元素放到堆顶，进行堆排序。可以看成是对最后一个元素的下沉操作。具体来说，每次会比较当前parent节点是否比左右节点大，如果是则结束。否则将parent节点和要左右中最大的节点交换， 然后从那个最大节点的索引位置继续往下比较，直到树又恢复成一颗最大堆树。 时间复杂度：$O(logn)$，每次向下调整涉及的步骤与树的高度有关

    private mutating func siftDown(from index: Int) {
        var parentIndex = index
        let count = heap.count
        let parentValue = heap[parentIndex]

        while true {
            let leftChildIndex = self.leftChildIndex(of: parentIndex)
            let rightChildIndex = leftChildIndex + 1
            var firstIndex = parentIndex

            if leftChildIndex < count && heap[leftChildIndex] > heap[firstIndex] {
                firstIndex = leftChildIndex
            }
            
            if rightChildIndex < count && heap[rightChildIndex] > heap[firstIndex] {
                firstIndex = rightChildIndex
            }

            if firstIndex == parentIndex {
                return
            }

            heap[parentIndex] = heap[firstIndex]
            heap[firstIndex] = parentValue
            parentIndex = firstIndex
        }
    }

创建操作

最大堆的创建有两种方法：

  1. 第一种是先创建一个空堆，然后根据元素逐一插入。插入的时间复杂度为 $O(log_2n)$，插入n个元素的话，总时间复杂度会达到$O(nlog_2n)$
  2. 第二种的话可以先将这n个元素顺序放入一个二叉树中形成完全二叉树，然后开始调整节点来满足最大堆性质，找到最后一个非叶节点即可($n/2 - 1$)，这样做的话复杂度啊可以降到$O(n)$，等效于做堆排序。
    private func buildMaxHeap() {
        let startIndex = (heap.count / 2) - 1
        for i in stride(from: startIndex, through: 0, by: -1) {
            siftDown(i)
        }
    }

总结

  • 最大堆其实可以看成是一种优先队列的实现，能在$O(logn)$时间复杂度下进行插入和提取最大值
  • 通过自底向上的buildMaxHeap方法，可以在$O(n)$时间内构建最大堆，比逐个插入的$O(nlogn)$ 更高效。