二进制堆(binary heap)

一个二进制堆是一个完全二叉树结构，它要么是最小堆，要么是最大堆。在最大堆中，根部的键必须是堆中所有键的最大值，对于二叉树中的所有节点，同样的属性必须是递归的。最小堆与最大堆类似。 比如这是一个最大堆：

1
2
3
4
5

    10
   /  \
  5    3
 / \
4   1

用数组表示堆

由于二进制堆是一个完全二叉树，所以它可以很容易地被表示为一个数组，使用数组表示可以节省空间。如果父节点存储在索引i处，那么左子节点就在2 * i + 1处，右子节点在2 * i + 2处，比如：

1
2
3
4
5

     10(0)
    /  \
   5(1) 3(2)
  / \
4(3) 1(4)

如何构造堆

heapify操作

我们以一个最大堆为例看看如何构造一个堆，这里是指从一个完全二叉树进行构造。
简单起见，我们先从一个只有三个节点的完全二叉树开始。

1
2
3

  7
 / \
2   4

如上，如果根结点元素已经是最大的，我们不需要任何操作；

1
2
3

  2             7
 / \    ->     / \
7   4         2   4

如果存在比根结点大的子节点，就需要交换以保持最大堆属性，也就是把顶层元素下降到合适的位置，这个操作称为heapify。
再来看另一种情况：

1
2
3
4
5

     2
   /   \
  10    9
 /  \   |
5    6  1

顶层元素不满足最大堆的约束，但所有的子树都是最大堆，和前边三个元素的树的思路一样，我们需要把顶层元素2下降到合适的位置：

  1. 找到2的子节点中比较大的那个，即10，交换之
1
2
3
4
5

     10
   /    \
  2      9
 / \     |
5   6    1
  1. 继续上一步操作，这次是6
1
2
3
4
5

     10
   /    \
  6      9
 / \     |
5   2    1
  1. 2已经在叶节点，结束

我们可以看到：在两个子树都是最大堆的树中保持最大堆属性，我们需要在根元素上反复运行heapify，直到它比它的子元素大，或者它成为叶节点，写成代码就是：

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

func Heapify(arr []int, n int, i int) {
    largest := i
    l := 2 * i + 1
    r := 2 * i + 2
  
    if l < n && arr[l] > arr[largest] {
        largest = l
    }
    if r < n && arr[r] > arr[largest] {
        largest = r
    }
  
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        // 递归对子树进行 heapify 操作
        Heapify(arr, n, largest)
    }
}

构建堆

有了heapify这个函数之后我们就可以着手从一个完全二叉树构建出一个堆了，其思路就是从底层开始对每个子树进行heapify操作，在heapify函数应用于包括根节点在内的所有节点之后，我们就得到了一个最大堆。
对于一棵完全二叉树，最后一个非叶子节点的索引是n / 2 - 1，之后的节点都是叶子节点，它们不需要heapify操作，所以只需要从n / 2 - 1向前一直遍历到根元素就可以了：

1
2
3
4
5

func BuildHeap(arr[] int, n int) {
    for i := n / 2 - 1; i >= 0; i-- {
        Heapify(arr, n, i)
    }
}

堆排序

堆排序有点类似于选择排序，只不过选择的过程利用了堆结构。
以从小到大的排序为例，我们可以用下述过程：

  1. 创建最大堆，此时最大的元素在根结点上，相当于我们利用一个最大堆选择出了最大值
  2. 把根结点上的最大元素和堆尾元素互换
  3. 将堆的尺寸缩小1，后边的元素已经排好序了，操作前边的元素就可以
  4. 由于把堆尾元素放到了根结点上，不能保证它是最大的，而左右子树都是最大堆
    此时利用heapify调整根结点，再次将二叉树变成最大堆
  5. 重复步骤2到步骤4，直到列表中的所有项目都被排序
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package main

import "fmt"

func main() {
    arr := []int{1, 12, 9, 5, 6, 10}
    n := len(arr)
    BuildHeap(arr, n)

    for i := n - 1; i >= 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        Heapify(arr, i, 0)
    }

    fmt.Println(arr)
}

func BuildHeap(arr[] int, n int) {
    for i := n / 2 - 1; i >= 0; i-- {
        Heapify(arr, n, i)
    }
}

func Heapify(arr []int, n int, i int) {
    largest := i
    l := 2 * i + 1
    r := 2 * i + 2
  
    if l < n && arr[l] > arr[largest] {
        largest = l
    }
    if r < n && arr[r] > arr[largest] {
        largest = r
    }
  
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        // 递归对子树进行 heapify 操作
        Heapify(arr, n, largest)
    }
}

堆排序在所有情况下（最佳情况、平均情况和最差情况）都有 O(nlog n) 的时间复杂度。这里只分析一下最差情况，其他情况分析思路相差不多。
在最差情况下，每一次Heapify操作都会将一个元素从当前位置移动到叶节点，需要进行log(n)次的比较和交换：

  1. BuildHeap阶段，需要为n/2个元素做Heapify操作，所以BuildHeap步骤的最坏情况的时间复杂度是n/2*log(n) ~ nlog(n)
  2. 排序阶段，我们将根元素与最后一个元素交换，然后对根元素进行Heapify操作。因为我们重复了n次，所以排序步骤的时间复杂度也是nlog(n)