堆排序算法及用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],葉子節點中下標最小的是n2n2, 非葉子節點中下標最大的是n21n21
(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(logn)。函數build_max_heap自底向上的調用max_heapify, 最終整個數組滿足最大堆,迭代過程的複雜度爲O(nlogn)O(nlogn), 因此整個函數的最壞時間複雜度也是O(nlogn)O(nlogn)。 而如果當前數組已經是最大堆了,例如數組原本是降序排列的, 那麼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(nlogn), 所以整個算法的最好最壞和平均時間複雜度都是O(nlogn)O(nlogn)。
堆排序算法的空間複雜度是O(1)O(1),從實現上很容易看出來。
相關文章
-
C#排序算法之堆排序
關於C#排序算法的堆排序具體是怎麼樣的呢?下面小編爲大家整理了C#排序算法之堆排序,希望能幫到大家! 一、基本概念堆:這裏是指一種數據結構,而不是我們在C#中提到的用於存儲引用類型對象的地方。它可以被當成一棵完全二叉 -
關於php堆排序實現原理與應用方法
這裏以php作爲描述語言較詳細講解堆排序原理,因保證程序可讀性,故不做優化,php程序中關於堆的一些概念如下:假設n爲當前數組的key則,n的父節點爲 n>>1 或者 n/2(整除);n的左子節點l= n<<1 或 l=n*2,n的右子節點r=(n<< -
內部排序之堆排序的實現
堆排序(Heap Sort)只需要一個記錄大小的輔助空間,每個待排序的記錄僅佔有一個存儲空間。下面小編爲大家整理了內部排序之堆排序的實現,希望能幫到大家! (1)基本概念a)堆:設有n個元素的序列:{k1, k2, ..., kn}對所有的i=1,2,. -
石精嘛尼堆堆散文
四川木裏藏族自治縣瓦科大路邊有一字兒排着十三個嘛尼堆堆(嘛尼堆:藏區路口要道常見的一種宗教設置物,用石頭堆砌成長,寬各丈餘的塔形,凡路過者要隨手拾一石塊添置堆上,念一句“阿嘛尼邊邊宏”,以表示對佛爺的祈禱和膜拜)。傳 -
java堆排序的算法思想的分析
一、基礎知識我們通常所說的堆是指二叉堆,二叉堆又稱完全二叉樹或者叫近似完全二叉樹。二叉堆又分爲最大堆和最小堆。堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法,它是選擇排序的一種。可以利用數組的 -
堆的javascript實現方法
堆的定義最大(最小)堆是一棵每一個節點的鍵值都不小於(大於)其孩子(如果存在)的鍵值的樹。大頂堆是一棵完全二叉樹,同時也是一棵最大樹。小頂堆是一棵完全完全二叉樹,同時也是一棵最小樹。另外,記住這兩個概念,對寫代碼太重要了 -
詳解C/C++中堆和棧及靜態數據區
本文是本站小編搜索整理的關於詳解C/C++中堆和棧及靜態數據區,供參考學習,希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網! 五大內存分區在C++中,內存分成5個區,他們分別是堆、棧、自由存儲區 -
快速排序算法及C#版的實現示例
殭屍是中國民間傳說的一種妖物之一,傳說已經死去人的屍體詐屍變成殭屍,身體僵硬,跳走行走,雙手豎直,面色蒼白以下是本站小編爲你整理的關於關於殭屍的傳奇故事,歡迎大家閱讀。《餵奶的殭屍》有個村莊裏住着一對夫婦,他們相親 -
c語言指針運用中堆和棧的區別
堆和棧的第一個區別就是申請方式不同:棧(英文名稱是stack)是系統自動分配空間的,例如我們定義一個 char a;系統會自動在棧上爲其開闢空間。而堆(英文名稱是heap)則是程序員根據需要自己申請的空間,例如malloc(10);由於棧 -
計算機二級《C++》考點解析:堆和類數組
爲幫助同學們更好更有準備地複習計算機二級C++,以下是本站小編搜索整理的計算機二級《C++》考點解析:堆和類數組,供參考複習,希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網! 一、構造函數和析