堆

只要满足这两点，它就是一个堆：

• 堆是一个完全二叉树；
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

堆化

在往堆中插入或删除一个元素时，让其重新满足堆的特性的过程，叫做堆化（heapify）。
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。

• 从下往上堆化，用于插入一个元素时。
• 从上往下堆化，用于删除一个元素时。

如何实现一个堆

堆的存储和二叉树一样，也是两种方法，数组存储法和链表存储法。

1. 往堆中插入一个元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

type Heap struct {
    a     []int // 数组，从下标1开始存储数据
    n     int   // 堆可以存储的最大数据个数
    count int   // 堆中已经存储的数据个数
}
func NewHeap(capacity int) *Heap {
    heap := &Heap{}
    heap.n = capacity
    heap.a = make([]int, capacity+1)
    heap.count = 0
    return heap
}
//大顶堆 -> 由下往上堆化
func (heap *Heap) insert(data int) {
    if heap.count == heap.n { // 堆满了
        return
    }
    heap.count++
    heap.a[heap.count] = data
    i := heap.count
    for i/2 > 0 && heap.a[i] > heap.a[i/2] {
        swap(heap.a, i, i/2)
        i = i / 2
    }
}

2. 删除堆顶元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func (heap *Heap) removeMax() {
    if heap.count == 0 { return } // 堆中没有数据
    a[1] = a[heap.count]
    heap.count--
    heapifyUpToDown(heap.a, heap.count, 1)
}

func heapifyUpToDown(a []int, n, i int) {
    for {
        maxIndex := i
        if i*2 <= n && a[i] < a[i*2] { maxIndex = i * 2 }
        if i*2+1 <= n && a[maxIndex] < a[i*2+1] { maxIndex = i*2 + 1 }
        if maxIndex == i { break }
        swap(a, i, maxIndex)
        i = maxIndex
    }
}

3. 时间复杂度分析 一个包含 n 个节点的完全二叉树，树的高度不会超过 $log_2 n$。
   堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 $O(logn)$。
   插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 $O(logn)$。

如何基于堆实现排序？

堆排序是一种原地的、时间复杂度为 O(nlogn) 的不稳定的排序算法。

1. 建堆：将数组原地建成一个堆。

1
2
3
4
5

func buidHeap(a []int, n int) {
    for i := n / 2; i >= 1; i-- {
        heapifyUpToDown(a, n, i)
    }
}

对于完全二叉树来说，下标从 2n+1 到 n 的都是叶子节点，这个结论是怎么推导出来的呢？

• 证明前提：从数组下标为1开始存储数据，数组下标为i的节点，左子节点为2i, 右子节点为2i + 1
• 证明方法：反证法
• 如果下标为n/2 + 1的节点不是叶子节点，即它存在子节点，按照【证明前提】，它的左子节点为：2(n/2 + 1) = n + 2，大家明显可以看出，这个数字已经大于n + 1，超出了实现完全二叉树所用数组的大小
  • 左子节点都已经超出了数组容量，更何况右子节点。
• 以此类推，很容易得出：下标大于n/2 + 1的节点肯定都是也叶子节点了
• 故而得出结论：对于完全二叉树来说，下标从n/2 + 1 到 n的节点都是叶子节点

时间复杂度分析：

• 因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。
• 每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。

                   节点个数         高度
       ()   ------  2^0       *     h
      /  \   
    ()    ()  ----  2^1       *     h-1
   /  \  /  \
  ()  ()()  () ---  2^2       *     h-2
       ...          ...             ...
                    2^k       *     h-k
                    ...             ...
                    2^(h-1)   *      1
  

• 计算各层需要比较和交换的节点数的累计和
  • $S1=1h+2^1(h-1)+2^2*(h-2)+…+2^k*(h-k)+…+2^{h-1}*1$
  • $S2=2S1=2^1(h)+2^2*(h-1)+…+2^k*(h-k+1)+…+2^{h-1}2+2^h1$
  • $S=S2-S1=-h+2+2^2+2^3+…+2^k+…+2^{h-1}+2^h$
  • $S=-h+(2^h-2)+2^h=2^{h+1}-h-2$
• 因为 $h=log_2 n$，代入公式S，就能得到 $S=O(n)$
• 所以，建堆的时间复杂度是： O(n)

2. 排序

• 数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
• 当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。
• 堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// n表示数据的个数，数组a中的数据从下标1到n的位置。
func sort(a []int, n int) {
    if n >= len(a) {
        n = len(a) - 1
    }
    buidHeap(a, n)

    k := n
    for k > 1 {
        swap(a, 1, k)
        k--
        heapifyUpToDown(a, k, 1)
    }
}

时间复杂度分析：$O(nlogn)$

在实际开发中，为什么快速排序要比堆排序性能好？

• 第一点，堆排序数据访问的方式没有快速排序友好。
  • 对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的，这对 CPU 缓存不友好。
• 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
  • 快速排序数据交换的次数不会比逆序度多。
  • 堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。

上一篇 « 二叉查找树 下一篇 » 2-3-4树