欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

解讀堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆排序示例

 更新時間:2016年06月08日 10:46:34   投稿:goldensun  
把待排序的數(shù)組構(gòu)造出最大堆是進(jìn)行堆排序操作的基本方法,這里將帶大家來解讀堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆排序示例,首先從堆排序的概念開始:

1、堆排序定義
n個關(guān)鍵字序列Kl,K2,…,Kn稱為堆,當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì)):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   )
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu),則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。
【例】關(guān)鍵字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分別滿足堆性質(zhì)(1)和(2),故它們均是堆,其對應(yīng)的完全二叉樹分別如最小堆示例和最大堆示例所示。
堆排序算法

201668104003619.png (522×378)

2、最大堆和最小堆
(1)根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為最小堆。
(2)結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者,稱為最大堆。
注意:
(1)堆中任一子樹亦是堆。
(2)以上討論的堆實(shí)際上是二叉堆(Binary Heap),類似地可定義k叉堆。

3、堆排序的基本思路如下:
(1)把待排序數(shù)組構(gòu)造成一個最大堆
(2)取出樹的根(最大(小)值, 實(shí)際算法的實(shí)現(xiàn)并不是真正的取出)
(3)將樹中剩下的元素再構(gòu)造成一個最大堆(這里的構(gòu)造和第1步不一樣,具體看實(shí)現(xiàn)部分)
(4)重復(fù)2,3操作,直到取完所有的元素
(5)把元素按取出的順序排列,即得到一個有序數(shù)組(在代碼實(shí)現(xiàn)里是通過交換操作"無形中"完成的)
在開始實(shí)現(xiàn)算法先看幾個結(jié)論(證明略):
(1)完全二叉樹A[0:n-1]中的任意節(jié)點(diǎn),其下標(biāo)為 ii, 那么其子節(jié)點(diǎn)的下標(biāo)分別是為2i+12i+1 和 2(i+1)2(i+1)
(2)大小為n的完全二叉樹A[0:n-1],葉子節(jié)點(diǎn)中下標(biāo)最小的是⌊n2⌋⌊n2⌋, 非葉子節(jié)點(diǎn)中下標(biāo)最大的是⌊n2⌋−1⌊n2⌋−1
(3)如果數(shù)組是一個最大堆,那么最大元素就是A[0]
(4)最大堆中任意節(jié)點(diǎn)的左右子樹也是最大堆
 
4、實(shí)現(xiàn)示例
這里的算法實(shí)現(xiàn)使用的是最大堆,首先來解決由數(shù)組建立最大堆的問題:

// 用于計算下標(biāo)為i的節(jié)點(diǎn)的兩個子節(jié)點(diǎn)的下標(biāo)值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
         
/* 此函數(shù)把一顆二叉樹中以node為根的子樹變成最大堆。
 * 注意: 使用的前提條件是 node節(jié)點(diǎn)的左右子樹(如果存在的話)都是最大堆。
 * 這個函數(shù)是整個算法的關(guān)鍵。
 */
void max_heapify(int heap[], int heap_size, int node)
{
  // 這里先不考慮整數(shù)溢出的問題
  // 先把注意力放在主要的功能上
  // 如果數(shù)據(jù)規(guī)模夠大,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);
 
    // 之后還要保證被交換的子節(jié)點(diǎn)構(gòu)成的子樹仍然是最大堆
    // 如果不是這個節(jié)點(diǎn)會繼續(xù)"下沉",直到合適的位置
    max_heapify(heap, heap_size, max_value);
  }
}
 
/* 將一個數(shù)組構(gòu)造成最大堆
 * 自底向上的利用max_heapify函數(shù)處理
 */
void build_max_heap(int heap[], int heap_size)
{
  if (heap_size < 2)
  {
    return;
  }
  int first_leaf = heap_size >> 1;//第一個葉子節(jié)點(diǎn)的下標(biāo)
 
  int i;
  // 從最后一個非葉子節(jié)點(diǎn)開始自底向上構(gòu)建,
  // 葉子節(jié)點(diǎn)都看作最大堆,因此可以使用max_heapify函數(shù)
  for (i = first_leaf - 1; i >= 0; i--)
  {
    max_heapify(heap, heap_size, i);
  }
}

函數(shù)max_heapify將指定子樹的根節(jié)點(diǎn)"下沉"到合適的位置, 最終子樹變成最大堆, 該過程最壞時間復(fù)雜度為O(logn)O(log⁡n)。函數(shù)build_max_heap自底向上的調(diào)用max_heapify, 最終整個數(shù)組滿足最大堆,迭代過程的復(fù)雜度為O(nlogn)O(nlog⁡n), 因此整個函數(shù)的最壞時間復(fù)雜度也是O(nlogn)O(nlog⁡n)。 而如果當(dāng)前數(shù)組已經(jīng)是最大堆了,例如數(shù)組原本是降序排列的, 那么max_heapify過程的時間復(fù)雜度就是O(1)O(1), 此時build_max_heap的時間復(fù)雜度是O(n)O(n),這是最好的情況。

接著實(shí)現(xiàn)堆排序過程:

/* heap sort 主函數(shù)
 */
void heap_sort(int heap[], int heap_size)
{
  if (heap == NULL || heap_size < 2)
  {
    return;
  }
  //構(gòu)建最大堆
  build_max_heap(heap, heap_size);
 
  int i;
  for (i = heap_size - 1; i > 0; i--)
  {
    /* 把當(dāng)前樹的根節(jié)點(diǎn)交換到末尾
     * 相當(dāng)于取出最大值,樹的規(guī)模變小。
     * 交換后的樹不是最大堆,但是根的兩顆子樹依然是最大堆
     * 滿足調(diào)用max_heapify的條件。之所以這樣交換,
     * 是因為用max_heapify處理時間復(fù)雜度較低,
     * 如果不交換而直接"取出"heap[0], 此處可能要使用
     * build_max_heap重新建立最大堆,時間復(fù)雜度較大
     */
    swap_val(heap, heap + i);
 
    heap_size--;
    //維護(hù)最大堆
    max_heapify(heap, heap_size, 0);
  }
}

最終的堆排序算法中,build_max_heap的復(fù)雜度是已知的, 迭代部分和build_max_heap的實(shí)現(xiàn)類似,而且不難看出, 交換后的根元素在下一次建堆過程中必然下沉到堆底,因此無論情況好壞, 該迭代過程時間復(fù)雜度都是O(nlogn)O(nlog⁡n), 所以整個算法的最好最壞和平均時間復(fù)雜度都是O(nlogn)O(nlog⁡n)。
堆排序算法的空間復(fù)雜度是O(1)O(1),從實(shí)現(xiàn)上很容易看出來。

相關(guān)文章

  • 關(guān)于C++友元類的實(shí)現(xiàn)講解

    關(guān)于C++友元類的實(shí)現(xiàn)講解

    今天小編就為大家分享一篇關(guān)于關(guān)于C++友元類的實(shí)現(xiàn)講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • C++解密Chrome80版本數(shù)據(jù)庫的方法示例代碼

    C++解密Chrome80版本數(shù)據(jù)庫的方法示例代碼

    這篇文章主要介紹了C++解密Chrome80版本數(shù)據(jù)庫的方法示例代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-05-05
  • C語言使用libZPlay錄制聲音并寫到文件的方法

    C語言使用libZPlay錄制聲音并寫到文件的方法

    這篇文章主要介紹了C語言使用libZPlay錄制聲音并寫到文件的方法,實(shí)例分析了C語言操作音頻文件的相關(guān)技巧,需要的朋友可以參考下
    2015-06-06
  • C語言中的強(qiáng)符號和弱符號介紹

    C語言中的強(qiáng)符號和弱符號介紹

    這篇文章主要介紹了C語言中的強(qiáng)符號和弱符號介紹,本文用多個實(shí)例來講解強(qiáng)符號和弱符號,需要的朋友可以參考下
    2015-03-03
  • C++命名空間實(shí)例解析

    C++命名空間實(shí)例解析

    這篇文章主要介紹了C++命名空間實(shí)例解析,對C++程序員來說是非常重要的知識點(diǎn),需要的朋友可以參考下
    2014-08-08
  • C語言可變參數(shù)函數(shù)詳解

    C語言可變參數(shù)函數(shù)詳解

    在某些情況下我們希望函數(shù)的參數(shù)個數(shù)可以根據(jù)需要確定,因此c語言引入可變參數(shù)函數(shù)。典型的可變參數(shù)函數(shù)的例子有printf()、scanf()等,下面我就開始講解
    2021-08-08
  • C++派生訪問說明符小記(推薦)

    C++派生訪問說明符小記(推薦)

    下面小編就為大家?guī)硪黄狢++派生訪問說明符小記(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • 淺析C++字節(jié)對齊容易被忽略的兩個問題

    淺析C++字節(jié)對齊容易被忽略的兩個問題

    今天我就和大家分享一下C++字節(jié)對齊容易被忽略的兩個問題。以下問題也是我實(shí)際開發(fā)工作中遇到的,如果有不同意見歡迎交流
    2013-07-07
  • C++ 中的Swap函數(shù)寫法匯總

    C++ 中的Swap函數(shù)寫法匯總

    這篇文章主要介紹了C++ 中的Swap函數(shù)寫法匯總,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-02-02
  • 一篇文章帶你了解C語言文件操作中的幾個函數(shù)

    一篇文章帶你了解C語言文件操作中的幾個函數(shù)

    這篇文章主要介紹了使用C語言操作文件的基本函數(shù)整理,包括創(chuàng)建和打開以及關(guān)閉文件的操作方法,需要的朋友可以參考下,希望能夠給你帶來幫助
    2021-09-09

最新評論