Heap Sort - 堆排序

堆排序通常基于二叉堆 实现，以大根堆为例，堆排序的实现过程分为两个子过程。第一步为取出大根堆的根节点(当前堆的最大值), 由于取走了一个节点，故需要对余下的元素重新建堆。重新建堆后继续取根节点，循环直至取完所有节点，此时数组已经有序。基本思想就是这样，不过实现上还是有些小技巧的。

堆的操作

以大根堆为例，堆的常用操作如下。

  1. 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  2. 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  3. 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

其中步骤1是给步骤2和3用的。

Heapsort-example

建堆时可以自顶向下，也可以采取自底向上，以下先采用自底向上的思路分析。我们可以将数组的后半部分节点想象为堆的最下面的那些节点，由于是单个节点，故显然满足二叉堆的定义，于是乎我们就可以从中间节点向上逐步构建二叉堆，每前进一步都保证其后的节点都是二叉堆，这样一来前进到第一个节点时整个数组就是一个二叉堆了。下面用 C++/Java 实现一个堆的类。C++/Java 中推荐使用 PriorityQueue 来使用堆。

堆排在空间比较小(嵌入式设备和手机)时特别有用，但是因为现代系统往往有较多的缓存，堆排序无法有效利用缓存，数组元素很少和相邻的其他元素比较，故缓存未命中的概率远大于其他在相邻元素间比较的算法。但是在海量数据的排序下又重新发挥了重要作用，因为它在插入操作和删除最大元素的混合动态场景中能保证对数级别的运行时间。TopM

C++

  1. #include <iostream>
  2. #include <vector>
  4. using namespace std;
  6. class HeapSort {
  7.     // get the parent node index
  8.     int parent(int i) {
  9.         return (i - 1) / 2;
  10.     }
  12.     // get the left child node index
  13.     int left(int i) {
  14.         return 2 * i + 1;
  15.     }
  17.     // get the right child node index
  18.     int right(int i) {
  19.         return 2 * i + 2;
  20.     }
  22.     // build max heap
  23.     void build_max_heapify(vector<int> &nums, int heap_size) {
  24.         for (int i = heap_size / 2; i >= 0; --i) {
  25.             max_heapify(nums, i, heap_size);
  26.         }
  27.         print_heap(nums, heap_size);
  28.     }
  30.     // build min heap
  31.     void build_min_heapify(vector<int> &nums, int heap_size) {
  32.         for (int i = heap_size / 2; i >= 0; --i) {
  33.             min_heapify(nums, i, heap_size);
  34.         }
  35.         print_heap(nums, heap_size);
  36.     }
  38.     // adjust the heap to max-heap
  39.     void max_heapify(vector<int> &nums, int k, int len) {
  40.         // int len = nums.size();
  41.         while (k < len) {
  42.             int max_index = k;
  43.             // left leaf node search
  44.             int l = left(k);
  45.             if (l < len && nums[l] > nums[max_index]) {
  46.                 max_index = l;
  47.             }
  48.             // right leaf node search
  49.             int r = right(k);
  50.             if (r < len && nums[r] > nums[max_index]) {
  51.                 max_index = r;
  52.             }
  53.             // node after k are max-heap already
  54.             if (k == max_index) {
  55.                 break;
  56.             }
  57.             // keep the root node the largest
  58.             int temp = nums[k];
  59.             nums[k] = nums[max_index];
  60.             nums[max_index] = temp;
  61.             // adjust not only just current index
  62.             k = max_index;
  63.         }
  64.     }
  66.     // adjust the heap to min-heap
  67.     void min_heapify(vector<int> &nums, int k, int len) {
  68.         // int len = nums.size();
  69.         while (k < len) {
  70.             int min_index = k;
  71.             // left leaf node search
  72.             int l = left(k);
  73.             if (l < len && nums[l] < nums[min_index]) {
  74.                 min_index = l;
  75.             }
  76.             // right leaf node search
  77.             int r = right(k);
  78.             if (r < len && nums[r] < nums[min_index]) {
  79.                 min_index = r;
  80.             }
  81.             // node after k are min-heap already
  82.             if (k == min_index) {
  83.                 break;
  84.             }
  85.             // keep the root node the largest
  86.             int temp = nums[k];
  87.             nums[k] = nums[min_index];
  88.             nums[min_index] = temp;
  89.             // adjust not only just current index
  90.             k = min_index;
  91.         }
  92.     }
  94. public:
  95.     // heap sort
  96.     void heap_sort(vector<int> &nums) {
  97.         int len = nums.size();
  98.         // init heap structure
  99.         build_max_heapify(nums, len);
  100.         // heap sort
  101.         for (int i = len - 1; i >= 0; --i) {
  102.             // put the largest number int the last
  103.             int temp = nums[0];
  104.             nums[0] = nums[i];
  105.             nums[i] = temp;
  106.             // reconstruct heap
  107.             build_max_heapify(nums, i);
  108.         }
  109.         print_heap(nums, len);
  110.     }
  112.     // print heap between [0, heap_size - 1]
  113.     void print_heap(vector<int> &nums, int heap_size) {
  114.         for (int i = 0; i < heap_size; ++i) {
  115.             cout << nums[i] << ", ";
  116.         }
  117.         cout << endl;
  118.     }
  119. };
  121. int main(int argc, char *argv[])
  122. {
  123.     int A[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
  124.     vector<int> nums;
  125.     for (int i = 0; i < sizeof(A) / sizeof(A[0]); ++i) {
  126.         nums.push_back(A[i]);
  127.     }
  129.     HeapSort sort;
  130.     sort.print_heap(nums, nums.size());
  131.     sort.heap_sort(nums);
  133.     return 0;
  134. }

Java

  1. import java.util.*;
  3. public class HeapSort {
  4.     // sign = 1 ==> min-heap, sign = -1 ==> max-heap
  5.     private void siftDown(int[] nums, int k, int size, int sign) {
  6.         int half = (size >>> 1);
  7.         while (k < half) {
  8.             int index = k;
  9.             // left leaf node search
  10.             int l = (k << 1) + 1;
  11.             if (l < size && (sign * nums[l]) < (sign * nums[index])) {
  12.                 index = l;
  13.             }
  14.             // right leaf node search
  15.             int r = l + 1;
  16.             if (r < size && (sign * nums[r]) < (sign * nums[index])) {
  17.                 index = r;
  18.             }
  19.             // already heapify
  20.             if (k == index) break;
  21.             // keep the root node the smallest/largest
  22.             int temp = nums[k];
  23.             nums[k] = nums[index];
  24.             nums[index] = temp;
  25.             // adjust next index
  26.             k = index;
  27.         }
  28.     }
  30.     private void heapify(int[] nums, int size, int sign) {
  31.         for (int i = size / 2; i >= 0; i--) {
  32.             siftDown(nums, i, size, sign);
  33.         }
  34.     }
  36.     private void minHeap(int[] nums, int size) {
  37.         heapify(nums, size, 1);
  38.     }
  40.     private void maxHeap(int[] nums, int size) {
  41.         heapify(nums, size, -1);
  42.     }
  44.     public void sort(int[] nums, boolean ascending) {
  45.         if (ascending) {
  46.             // build max heap
  47.             maxHeap(nums, nums.length);
  48.             // heap sort
  49.             for (int i = nums.length - 1; i >= 0; i--) {
  50.                 int temp = nums[0];
  51.                 nums[0] = nums[i];
  52.                 nums[i] = temp;
  53.                 // reconstruct max heap
  54.                 maxHeap(nums, i);
  55.             }
  56.         } else {
  57.             // build min heap
  58.             minHeap(nums, nums.length);
  59.             // heap sort
  60.             for (int i = nums.length - 1; i >= 0; i--) {
  61.                 int temp = nums[0];
  62.                 nums[0] = nums[i];
  63.                 nums[i] = temp;
  64.                 // reconstruct min heap
  65.                 minHeap(nums, i);
  66.             }
  67.         }
  68.     }
  70.     public static void main(String[] args) {
  71.         int[] A = new int[]{19, 1, 10, 14, 16, 4, 4, 7, 9, 3, 2, 8, 5, 11};
  72.         HeapSort heapsort = new HeapSort();
  73.         heapsort.sort(A, true);
  74.         for (int i : A) {
  75.             System.out.println(i);
  76.         }
  77.     }
  78. }

复杂度分析

从代码中可以发现堆排最费时间的地方在于构建二叉堆的过程。

上述构建大根堆和小根堆都是自底向上的方法，建堆过程时间复杂度为 O(2N), 堆化过程(可结合图形分析，最多需要调整的层数为最大深度)时间复杂度为 \log i, 故堆排过程中总的时间复杂度为 O(N \log N).

先看看建堆的过程，画图分析(比如以8个节点为例)可知在最坏情况下，每次都需要调整之前已经成为堆的节点，那么就意味着有二分之一的节点向下比较了一次，四分之一的节点向下比较了两次，八分之一的节点比较了三次… 等差等比数列求和，具体过程可参考下面的链接。

Reference