二叉堆与堆排序

一般我们所说的堆通常指的是二叉堆，即结点的分布满足完全二叉树，一颗大小为N的完全二叉树高度为logN的向下取整。并且该二叉树中根节点的值大于其两个子节点，此时称其为最大堆；或者根节点的值小于两个子节点的值则称之为最小堆。由于其是一个完全的二叉树，通常使用一个数组存储每个节点。因此节点序号为k的节点其左右两个子节点的序号分别是2k和2k+1（从1位置开始存储）。

堆的算法

堆算法中最重要的便是堆的有序化，主要有两种情况。一是当某个节点的优先级上升或者在堆底部插入一个新的元素时，需要由下至上回复堆的顺序。二是当某个节点的优先级下降，如将根节点替换为一个较小的元素时，需要由上至下恢复堆的顺序。

由下至上的堆有序化（上浮）

若堆的有序状态因为某个节点变得比其父节点还大而被打破，则需要通过交换它和它的父节点来修复堆，并且如此递归操作使该节点不断上移，直至堆重新有序。实现如下：

1
2
3
4
5
6


void swim(int k) {
  while (k > 1 && arr[k/2] < arr[k]) {
    swap(arr[k/2], arr[k]);
    k = k/2;
  }
}

swim()方法中的循环保证了只有当k位置节点大于其父节点时，堆的有序性才会被打破。当该节点不大于其父节点时堆就有序了。

由上至下的堆有序化（下沉）

若堆的有序状态因为某个节点变得比其子节点小而被打破，则需要通过将其递归地与子节点中较大者交换，直至该节点的子节点都比其小或是到达底部，来恢复堆的有序化。实现如下：

1
2
3
4
5
6
7
8
9


void sink(int k) {
  while (2*k <= N) { //到达底层就不再比较
    int j = 2*k;
    if (j < N && arr[j] < arr[j+1]) j++; //j为最大子节点索引
    if (arr[k] >= arr[j]) break;
    swap(arr[k], arr[j]);
    k=j;
  }
}

基于以上两个基本操作，堆可以实现以下接口： 1. 插入元素：将新元素插至数组尾部，增加堆的大小并让新元素上浮到合适的位置。 2. 删除最大元素：从数组头部删除最大元素并将最后一个元素放到头部，减小堆的大小并该元素下沉到合适的位置。

堆的实现

 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


template<typename T>
class MaxHeap {
private:
  T* data; //堆数组指针
  int capacity; //堆大小
  int count; //元素个数

  void sink(int k) {
   while (2*k <= count) { //到达底层就不再比较
       int j = 2*k;
       if (j < count && data[j] < data[j+1]) j++; //j为最大子节点索引
       if (data[k] >= data[j]) break;
       swap(data[k], data[j]);
       k=j;
     }
  }

  void swim(int k) {
    while (k > 1 && data[k/2] < data[k]) {
       swap(data[k/2], data[k]);
       k = k/2;
    }
  }

public:
  MaxHeap(int capacity=3) {
    data = new T[capacity];
    int count = 0;
    this->capacity = capacity;
  }

  ~MaxHeap() {
    delete[] data;
  }

  //元素个数
  int size() { 
    return count;
  }
  //是否为空
  bool empty() {
    return count == 0;
  }

  void insert(T item) {
    if (count + 1 >= capacity) {
      T *oldData = data;
      data = new T[2*capacity];
      for (int i=1; i<capacity; i++) {
        data[i] = oldData[i];
      }
    }
    data[count+1] = item;
    count++;
    swim(count);
  }

  T pop() {
    T ret = data[1];
    swap(data[1], data[count]);
    count--;
    sink(1);
    return ret;
  }
}

对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过(logN+1)次比较，删除最大元素的操作只需不超过2logN次比较。

堆排序

堆排序主要分为两个阶段。在堆的构造阶段中，需要将原始数组重新安排进一个堆中。在下沉阶段，需要从堆中按递减顺序取出所有元素并得到排序结果。

由N个元素构造一个堆可以通过从左至右遍历数组，用swim()保证扫描指针左侧所有元素已经是一棵堆有序完全二叉树，就像连续向优先队列插入元素一样。但是一个更加有效的方法是从右至左用sink()函数构造子堆，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()可以将他们变成一个堆。开始时只需要扫描一般的数组，因为可以跳过大小为1的子堆。堆排序的主要工作都是在第二阶段完成的，主要实现是将堆中最大元素删除，放入堆缩小后数组中空出的位置。算法实现如下：

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


void sink(int arr, int i, int n) {
  while(i<=n) {
    int j = 2*i;
    if (j < n && arr[j] < arr[j+1]) j++;
    if (arr[i] >= arr[j]) break;
    swap(arr[i], arr[j]);
    i = j;
  }
}

heapSort(int arr[], int n) {
  for (int i = n/2; i >= 1; i--) { //构造堆——第一阶段
    sink(arr, i, n);
  while (n > 1) { //下沉——第二阶段
    swap(arr[1], n--);
    sink(arr, 1, n);
  }
}

将N个元素排序，堆排序只需要少于(2NlogN+2N)次比较，其中2N来自于堆的构造阶段，2NlogN来自于每次下沉操作最多需要2logN次比较。堆排序算法是一种能够同时最优利用空间和时间的算法，即使是最坏情况下也能够保证~2NlogN次比较和恒定的额外空间。

Contents

堆的算法

由下至上的堆有序化（上浮）

由上至下的堆有序化（下沉）

堆的实现

堆排序