C++ 大根堆排序?qū)W習筆記
什么是大根堆
大根堆是完全二叉樹,其中每個節(jié)點都比其子節(jié)點大,而根節(jié)點是最大的節(jié)點,所以稱為“大根” 堆;
大根堆排序則是基于大根堆實現(xiàn)的排序算法,基本思想是將待排序的序列組成一個大根堆,然后依次取出頂元素(即最大元素),并將剩余元素構(gòu)成新的大根堆,重復以上過程直到最后一個元素,就得到了完全排好序的序列。大根堆排序是一種原地排序算法,所以其空間復雜度為O(1),只需要常數(shù)級別的空間;而時間復雜度則為O(nlogn)
排序步驟
- 1 構(gòu)建大根堆
我們從序列的最后一個非葉子節(jié)點開始,依次將其與其子節(jié)點進行比較,如果有子節(jié)點比它大,則將它與最大的子節(jié)點交換位置,然后再以交換后的子節(jié)點作為根節(jié)點,繼續(xù)向下比較和交換,直到該節(jié)點成為葉子節(jié)點或者它的子節(jié)點都比它小為止。這樣就可以保證每個節(jié)點都比其子節(jié)點大,從而構(gòu)建成一個大根堆。
- 2 取出堆頂元素
由于大根堆的根節(jié)點是最大的元素,因此我們可以直接取出堆頂元素,并將其放到序列的末尾。
- 3 重新構(gòu)建大根堆
取出堆頂元素后,我們需要重新構(gòu)建剩余元素的大根堆。具體操作是將序列的第一個元素作為根節(jié)點,依次將其與其子節(jié)點進行比較,如果有子節(jié)點比它大,則將它與最大的子節(jié)點交換位置,然后再以交換后的子節(jié)點作為根節(jié)點,繼續(xù)向下比較和交換,直到該節(jié)點成為葉子節(jié)點或者它的子節(jié)點都比它小為止。這樣就可以保證剩余元素構(gòu)成一個新的大根堆。
- 4 重復執(zhí)行步驟2和步驟3
重復執(zhí)行步驟2和步驟3,直到所有元素都被取出,序列就由大到小排好了。
C++代碼實現(xiàn)
#include <iostream> #include <vector> // 打印數(shù)組 void printArr(std::vector<int>& arr, int len = 0); // 大根堆排序主方法 void heapify(std::vector<int>&, int, int); // 大根堆排序 void heapSort(std::vector<int>&); // 大堆排序 void heapify(std::vector<int>& arr, int len, int index) { int largest = index; std::cout << "設(shè)置當前節(jié)點arr[" << index << "]=" << arr[index] << "為根節(jié)點" << std::endl; int left = 2 * index + 1; std::cout << "左節(jié)點索引: " << left << std::endl; int right = 2 * index + 2; std::cout << "右節(jié)點索引: " << right << std::endl; if (left < len) { std::cout << "比較左節(jié)點arr[" << left << "]=" << arr[left] << "與根點節(jié)大小" << std::endl; } else { std::cout << "左節(jié)點超出范圍,即不存在" << std::endl; } if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len) { std::cout << "比較右節(jié)點arr[" << right << "]=" << arr[right] << "與根點節(jié)大小" << std::endl; } else { std::cout << "右節(jié)點超出范圍,即不存在" << std::endl; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != index) { std::cout << "根節(jié)點小于子節(jié)點,交換根(arr[" << index << "]=" << arr[index] << ")與子(arr[" << largest << "]=" << arr[largest] << ")節(jié)點" << std::endl; std::swap(arr[index], arr[largest]); printArr(arr, len); heapify(arr, len, largest); } } void heapSort(std::vector<int>& arr) { int len = arr.size(); // 構(gòu)建大根堆, 從最后一個非葉子節(jié)點向下調(diào)整 for (int i = len / 2 - 1; i >= 0; i--) { heapify(arr, len, i); } std::cout << "大根堆: "; printArr(arr); // 依次將堆頂元素與堆的最后一個元素交換,并調(diào)整堆 for (int i = len - 1; i > 0; i--) { std::cout << "將最大值(arr[0]=" << arr[0] << ")與最后元素(arr[" << i << "]=" << arr[i] << ")交換" << std::endl; std::swap(arr[0], arr[i]); std::cout << "重新設(shè)置大根堆: "; printArr(arr, i); heapify(arr, i, 0); } } void printArr(std::vector<int>& arr, int len) { std::cout << "{ "; if (len <= 0) { for (auto &&n : arr) { std::cout << n << " "; } } else { for (int i = 0; i < len; i++) { std::cout << arr[i] << " "; } } std::cout << "}" << std::endl; } int main() { std::vector<int> arr = {1, 39, 2, 66, 23, 5, 6, 9, 4, 8}; std::cout << "原數(shù)組: "; printArr(arr); heapSort(arr); std::cout << "排序后: "; printArr(arr); }
排序過程
編譯以上代碼后執(zhí)行,得到以下結(jié)果
原數(shù)組: { 1 39 2 66 23 5 6 9 4 8 }
設(shè)置當前節(jié)點arr[4]=23為根節(jié)點
左節(jié)點索引: 9
右節(jié)點索引: 10
比較左節(jié)點arr[9]=8與根點節(jié)大小
右節(jié)點超出范圍,即不存在
設(shè)置當前節(jié)點arr[3]=66為根節(jié)點
左節(jié)點索引: 7
右節(jié)點索引: 8
比較左節(jié)點arr[7]=9與根點節(jié)大小
比較右節(jié)點arr[8]=4與根點節(jié)大小
設(shè)置當前節(jié)點arr[2]=2為根節(jié)點
左節(jié)點索引: 5
右節(jié)點索引: 6
比較左節(jié)點arr[5]=5與根點節(jié)大小
比較右節(jié)點arr[6]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[2]=2)與子(arr[6]=6)節(jié)點
{ 1 39 6 66 23 5 2 9 4 8 }
設(shè)置當前節(jié)點arr[6]=2為根節(jié)點
左節(jié)點索引: 13
右節(jié)點索引: 14
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
設(shè)置當前節(jié)點arr[1]=39為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=66與根點節(jié)大小
比較右節(jié)點arr[4]=23與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=39)與子(arr[3]=66)節(jié)點
{ 1 66 6 39 23 5 2 9 4 8 }
設(shè)置當前節(jié)點arr[3]=39為根節(jié)點
左節(jié)點索引: 7
右節(jié)點索引: 8
比較左節(jié)點arr[7]=9與根點節(jié)大小
比較右節(jié)點arr[8]=4與根點節(jié)大小
設(shè)置當前節(jié)點arr[0]=1為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=66與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=1)與子(arr[1]=66)節(jié)點
{ 66 1 6 39 23 5 2 9 4 8 }
設(shè)置當前節(jié)點arr[1]=1為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=39與根點節(jié)大小
比較右節(jié)點arr[4]=23與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=1)與子(arr[3]=39)節(jié)點
{ 66 39 6 1 23 5 2 9 4 8 }
設(shè)置當前節(jié)點arr[3]=1為根節(jié)點
左節(jié)點索引: 7
右節(jié)點索引: 8
比較左節(jié)點arr[7]=9與根點節(jié)大小
比較右節(jié)點arr[8]=4與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[3]=1)與子(arr[7]=9)節(jié)點
{ 66 39 6 9 23 5 2 1 4 8 }
設(shè)置當前節(jié)點arr[7]=1為根節(jié)點
左節(jié)點索引: 15
右節(jié)點索引: 16
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
大根堆: { 66 39 6 9 23 5 2 1 4 8 }
將最大值(arr[0]=66)與最后元素(arr[9]=8)交換
重新設(shè)置大根堆: { 8 39 6 9 23 5 2 1 4 }
設(shè)置當前節(jié)點arr[0]=8為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=39與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=8)與子(arr[1]=39)節(jié)點
{ 39 8 6 9 23 5 2 1 4 }
設(shè)置當前節(jié)點arr[1]=8為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=9與根點節(jié)大小
比較右節(jié)點arr[4]=23與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=8)與子(arr[4]=23)節(jié)點
{ 39 23 6 9 8 5 2 1 4 }
設(shè)置當前節(jié)點arr[4]=8為根節(jié)點
左節(jié)點索引: 9
右節(jié)點索引: 10
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=39)與最后元素(arr[8]=4)交換
重新設(shè)置大根堆: { 4 23 6 9 8 5 2 1 }
設(shè)置當前節(jié)點arr[0]=4為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=23與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=4)與子(arr[1]=23)節(jié)點
{ 23 4 6 9 8 5 2 1 }
設(shè)置當前節(jié)點arr[1]=4為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=9與根點節(jié)大小
比較右節(jié)點arr[4]=8與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=4)與子(arr[3]=9)節(jié)點
{ 23 9 6 4 8 5 2 1 }
設(shè)置當前節(jié)點arr[3]=4為根節(jié)點
左節(jié)點索引: 7
右節(jié)點索引: 8
比較左節(jié)點arr[7]=1與根點節(jié)大小
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=23)與最后元素(arr[7]=1)交換
重新設(shè)置大根堆: { 1 9 6 4 8 5 2 }
設(shè)置當前節(jié)點arr[0]=1為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=9與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=1)與子(arr[1]=9)節(jié)點
{ 9 1 6 4 8 5 2 }
設(shè)置當前節(jié)點arr[1]=1為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=4與根點節(jié)大小
比較右節(jié)點arr[4]=8與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=1)與子(arr[4]=8)節(jié)點
{ 9 8 6 4 1 5 2 }
設(shè)置當前節(jié)點arr[4]=1為根節(jié)點
左節(jié)點索引: 9
右節(jié)點索引: 10
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=9)與最后元素(arr[6]=2)交換
重新設(shè)置大根堆: { 2 8 6 4 1 5 }
設(shè)置當前節(jié)點arr[0]=2為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=8與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=2)與子(arr[1]=8)節(jié)點
{ 8 2 6 4 1 5 }
設(shè)置當前節(jié)點arr[1]=2為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
比較左節(jié)點arr[3]=4與根點節(jié)大小
比較右節(jié)點arr[4]=1與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[1]=2)與子(arr[3]=4)節(jié)點
{ 8 4 6 2 1 5 }
設(shè)置當前節(jié)點arr[3]=2為根節(jié)點
左節(jié)點索引: 7
右節(jié)點索引: 8
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=8)與最后元素(arr[5]=5)交換
重新設(shè)置大根堆: { 5 4 6 2 1 }
設(shè)置當前節(jié)點arr[0]=5為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=4與根點節(jié)大小
比較右節(jié)點arr[2]=6與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=5)與子(arr[2]=6)節(jié)點
{ 6 4 5 2 1 }
設(shè)置當前節(jié)點arr[2]=5為根節(jié)點
左節(jié)點索引: 5
右節(jié)點索引: 6
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=6)與最后元素(arr[4]=1)交換
重新設(shè)置大根堆: { 1 4 5 2 }
設(shè)置當前節(jié)點arr[0]=1為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=4與根點節(jié)大小
比較右節(jié)點arr[2]=5與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=1)與子(arr[2]=5)節(jié)點
{ 5 4 1 2 }
設(shè)置當前節(jié)點arr[2]=1為根節(jié)點
左節(jié)點索引: 5
右節(jié)點索引: 6
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=5)與最后元素(arr[3]=2)交換
重新設(shè)置大根堆: { 2 4 1 }
設(shè)置當前節(jié)點arr[0]=2為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=4與根點節(jié)大小
比較右節(jié)點arr[2]=1與根點節(jié)大小
根節(jié)點小于子節(jié)點,交換根(arr[0]=2)與子(arr[1]=4)節(jié)點
{ 4 2 1 }
設(shè)置當前節(jié)點arr[1]=2為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=4)與最后元素(arr[2]=1)交換
重新設(shè)置大根堆: { 1 2 }
設(shè)置當前節(jié)點arr[0]=1為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
比較左節(jié)點arr[1]=2與根點節(jié)大小
右節(jié)點超出范圍,即不存在
根節(jié)點小于子節(jié)點,交換根(arr[0]=1)與子(arr[1]=2)節(jié)點
{ 2 1 }
設(shè)置當前節(jié)點arr[1]=1為根節(jié)點
左節(jié)點索引: 3
右節(jié)點索引: 4
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
將最大值(arr[0]=2)與最后元素(arr[1]=1)交換
重新設(shè)置大根堆: { 1 }
設(shè)置當前節(jié)點arr[0]=1為根節(jié)點
左節(jié)點索引: 1
右節(jié)點索引: 2
左節(jié)點超出范圍,即不存在
右節(jié)點超出范圍,即不存在
排序后: { 1 2 4 5 6 8 9 23 39 66 }
以上就是C++ 大根堆排序?qū)W習筆記的詳細內(nèi)容,更多關(guān)于C++ 大根堆排序的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
c語言_構(gòu)建一個靜態(tài)二叉樹實現(xiàn)方法
下面小編就為大家?guī)硪黄猚語言_構(gòu)建一個靜態(tài)二叉樹實現(xiàn)方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-05-05C語言與C++動態(tài)通訊錄超詳細實現(xiàn)流程
這篇文章主要為大家介紹了C語言與C++動態(tài)實現(xiàn)通訊錄,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2022-05-05