解讀堆排序算法及用C++完成基於最年夜堆的堆排序示例

解讀堆排序算法及用C++完成基於最年夜堆的堆排序示例。本站提示廣大學習愛好者：（解讀堆排序算法及用C++完成基於最年夜堆的堆排序示例）文章只能為提供參考，不一定能成為您想要的結果。以下是解讀堆排序算法及用C++完成基於最年夜堆的堆排序示例正文

1、堆排序界說
n個症結字序列Kl，K2，…，Kn稱為堆，當且僅當該序列知足以下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   )
若將此序列所存儲的向量R[1..n]看作是一棵完整二叉樹的存儲構造，則堆本質上是知足以下性質的完整二叉樹：樹中任一非葉結點的症結字均不年夜於(或不小於)其閣下孩子(若存在)結點的症結字。
【例】症結字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分離知足堆性質(1)和(2)，故它們均是堆，其對應的完整二叉樹分離如最小堆示例和最年夜堆示例所示。
堆排序算法

2、最年夜堆和最小堆
（1）根結點(亦稱為堆頂)的症結字是堆裡一切結點症結字中最小者的堆稱為最小堆。
（2）結點(亦稱為堆頂)的症結字是堆裡一切結點症結字中最年夜者，稱為最年夜堆。
留意：
（1）堆中任一子樹亦是堆。
（2）以上評論辯論的堆現實上是二叉堆(Binary Heap)，相似地可界說k叉堆。

3、堆排序的根本思緒以下:
（1）把待排序數組結構成一個最年夜堆
（2）掏出樹的根(最年夜(小)值, 現實算法的完成其實不是真實的掏出)
（3）將樹中剩下的元素再結構成一個最年夜堆(這裡的結構和第1步紛歧樣，詳細看完成部門)
（4）反復2,3操作，直到取完一切的元素
（5）把元素按掏出的次序分列，即獲得一個有序數組(在代碼完成裡是經由過程交流操作"有形中"完成的)
在開端完成算法先看幾個結論(證實略):
（1）完整二叉樹A[0:n-1]中的隨意率性節點，其下標為 ii, 那末其子節點的下標分離是為2i+12i+1 和 2(i+1)2(i+1)
（2）年夜小為n的完整二叉樹A[0:n-1]，葉子節點中下標最小的是⌊n2⌋⌊n2⌋， 非葉子節點中下標最年夜的是⌊n2⌋−1⌊n2⌋−1
（3）假如數組是一個最年夜堆，那末最年夜元素就是A[0]
（4）最年夜堆中隨意率性節點的閣下子樹也是最年夜堆
 
4、完成示例
這裡的算法完成應用的是最年夜堆，起首來處理由數組樹立最年夜堆的成績:

// 用於盤算下標為i的節點的兩個子節點的下標值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
         
/* 此函數把一顆二叉樹中以node為根的子樹釀成最年夜堆。
 * 留意: 應用的條件前提是 node節點的閣下子樹(假如存在的話)都是最年夜堆。
 * 這個函數是全部算法的症結。
 */
void max_heapify(int heap[], int heap_size, int node)
{
  // 這裡先不斟酌整數溢出的成績
  // 先把留意力放在重要的功效上
  // 假如數據范圍夠年夜,int類型必定會溢出
  int l_child = LEFT(node);
  int r_child = RIGHT(node);
  int max_value = node;
 
  if (l_child < heap_size && heap[l_child] > heap[max_value])
  {
    max_value = l_child;
  }
  if (r_child < heap_size && heap[r_child] > heap[max_value])
  {
    max_value = r_child;
  }
  if (max_value != node)
  {
    swap_val(heap + node, heap + max_value);
 
    // 以後還要包管被交流的子節點組成的子樹依然是最年夜堆
    // 假如不是這個節點會持續"下沉"，直到適合的地位
    max_heapify(heap, heap_size, max_value);
  }
}
 
/* 將一個數組結構成最年夜堆
 * 自底向上的應用max_heapify函數處置
 */
void build_max_heap(int heap[], int heap_size)
{
  if (heap_size < 2)
  {
    return;
  }
  int first_leaf = heap_size >> 1;//第一個葉子節點的下標
 
  int i;
  // 從最初一個非葉子節點開端自底向上構建，
  // 葉子節點都看做最年夜堆，是以可使用max_heapify函數
  for (i = first_leaf - 1; i >= 0; i--)
  {
    max_heapify(heap, heap_size, i);
  }
}

函數max_heapify將指定子樹的根節點"下沉"到適合的地位, 終究子樹釀成最年夜堆， 該進程最壞時光龐雜度為O(logn)O(log⁡n)。函數build_max_heap自底向上的挪用max_heapify, 終究全部數組知足最年夜堆，迭代進程的龐雜度為O(nlogn)O(nlog⁡n)， 是以全部函數的最壞時光龐雜度也是O(nlogn)O(nlog⁡n)。 而假如以後數組曾經是最年夜堆了，例如數組本來是降序分列的， 那末max_heapify進程的時光龐雜度就是O(1)O(1), 此時build_max_heap的時光龐雜度是O(n)O(n)，這是最好的情形。

接實在現堆排序進程：

/* heap sort 主函數
 */
void heap_sort(int heap[], int heap_size)
{
  if (heap == NULL || heap_size < 2)
  {
    return;
  }
  //構建最年夜堆
  build_max_heap(heap, heap_size);
 
  int i;
  for (i = heap_size - 1; i > 0; i--)
  {
    /* 把以後樹的根節點交流到末尾
     * 相當於掏出最年夜值，樹的范圍變小。
     * 交流後的樹不是最年夜堆，然則根的兩顆子樹仍然是最年夜堆
     * 知足挪用max_heapify的前提。之所以如許交流，
     * 是由於用max_heapify處置時光龐雜度較低，
     * 假如不交流而直接"掏出"heap[0], 此處能夠要應用
     * build_max_heap從新樹立最年夜堆，時光龐雜度較年夜
     */
    swap_val(heap, heap + i);
 
    heap_size--;
    //保護最年夜堆
    max_heapify(heap, heap_size, 0);
  }
}

終究的堆排序算法中，build_max_heap的龐雜度是已知的， 迭代部門和build_max_heap的完成相似，並且不好看出， 交流後的根元素鄙人一次建堆進程中必定下沉到堆底，是以不管情形利害， 該迭代進程時光龐雜度都是O(nlogn)O(nlog⁡n)， 所以全部算法的最好最壞戰爭均時光龐雜度都是O(nlogn)O(nlog⁡n)。
堆排序算法的空間龐雜度是O(1)O(1)，從完成上很輕易看出來。