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

C++ 大根堆排序?qū)W習筆記

 更新時間:2023年10月29日 15:49:07   作者:Totn  
這篇文章主要為大家介紹了C++ 大根堆排序的學習教程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

什么是大根堆

大根堆是完全二叉樹,其中每個節(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++編寫生成不重復的隨機數(shù)代碼

    C++編寫生成不重復的隨機數(shù)代碼

    本文給大家匯總介紹了3種c++實現(xiàn)生成不重復的隨機數(shù)的函數(shù),十分的簡單實用,有需要的小伙伴可以參考下。
    2015-05-05
  • C++實現(xiàn)字符串切割的兩種方法

    C++實現(xiàn)字符串切割的兩種方法

    這篇文章主要介紹了C++實現(xiàn)字符串切割的兩種方法,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-06-06
  • 深入解析C++ Data Member內(nèi)存布局

    深入解析C++ Data Member內(nèi)存布局

    本篇文章是對C++中的Data Member內(nèi)存布局進行了詳細的分析介紹,需要的朋友參考下
    2013-07-07
  • C語言實現(xiàn)隨機生成6位數(shù)密碼

    C語言實現(xiàn)隨機生成6位數(shù)密碼

    這篇文章主要為大家詳細介紹了如何使用C語言實現(xiàn)一個簡單而實用的隨機密碼生成器,該生成器將生成包含字母、數(shù)字和特殊字符的隨機密碼,有需要的小伙伴可以參考下
    2023-11-11
  • C++中生成隨機數(shù)的方法總結(jié)

    C++中生成隨機數(shù)的方法總結(jié)

    這篇文章主要介紹了C++中生成隨機數(shù)的方法總結(jié),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-05-05
  • c語言_構(gòu)建一個靜態(tài)二叉樹實現(xiàn)方法

    c語言_構(gòu)建一個靜態(tài)二叉樹實現(xiàn)方法

    下面小編就為大家?guī)硪黄猚語言_構(gòu)建一個靜態(tài)二叉樹實現(xiàn)方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05
  • C++常見異常處理原理及代碼示例解析

    C++常見異常處理原理及代碼示例解析

    這篇文章主要介紹了C++常見異常處理原理及代碼示例解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-07-07
  • C語言與C++動態(tài)通訊錄超詳細實現(xiàn)流程

    C語言與C++動態(tài)通訊錄超詳細實現(xiàn)流程

    這篇文章主要為大家介紹了C語言與C++動態(tài)實現(xiàn)通訊錄,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-05-05
  • C++多線程中的鎖和條件變量使用教程

    C++多線程中的鎖和條件變量使用教程

    這篇文章主要介紹了C++多線程中的鎖和條件變量使用,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下
    2018-11-11
  • 一文帶你搞懂C語言動態(tài)內(nèi)存管理

    一文帶你搞懂C語言動態(tài)內(nèi)存管理

    動態(tài)內(nèi)存是指在堆上分配的內(nèi)存,而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存。本文將通過幾個示例帶大家深入了解一下C語言的動態(tài)內(nèi)存管理,需要的可以參考一下
    2022-11-11

最新評論