Heap Sort - 堆排序

堆排序通常基於二元堆 實現，以大根堆(根結點為最大值)爲例，堆排序的實現過程分爲兩個子過程。第一步爲取出大根堆的根節點(當前堆的最大值), 由於取走了一個節點，故需要對餘下的元素重新建堆。重新建堆後繼續取根節點，循環直至取完所有節點，此時數組已經有序。基本思想就是這樣，不過實現上還是有些小技巧的。

堆的操作

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

  1. 最大堆調整（Max_Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
  2. 創建最大堆（Build_Max_Heap）：將堆所有數據重新排序
  3. 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

其中步驟1是給步驟2和3用的。

Heapsort-example

建堆時可以自頂向下，也可以採取自底向上，以下先採用自底向上的思路分析。我們可以將數組的後半部分節點想象爲堆的最下面的那些節點，由於是單個節點，故顯然滿足二叉堆的定義，於是乎我們就可以從中間節點向上逐步構建二叉堆，每前進一步都保證其後的節點都是二叉堆，這樣一來前進到第一個節點時整個數組就是一個二叉堆了。下面用 C++/Java 實現一個堆的類。C++/Java 中推薦使用 PriorityQueue 來使用堆。

堆排在空間比較小(嵌入式設備和手機)時特別有用，但是因爲現代系統往往有較多的快取，堆排序無法有效利用快取，數組元素很少和相鄰的其他元素比較，故快取未命中的機率遠大於其他在相鄰元素間比較的算法。但是在大數據的排序下又重新發揮了重要作用，因爲它在插入操作和刪除最大元素的混合動態場景中能保證對數級別的運行時間。

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