什么是大根堆

大根堆是完全二叉樹，其中每個(gè)節(jié)點(diǎn)都比其子節(jié)點(diǎn)大，而根節(jié)點(diǎn)是最大的節(jié)點(diǎn)，所以稱為“大根” 堆；

大根堆排序則是基于大根堆實(shí)現(xiàn)的排序算法，基本思想是將待排序的序列組成一個(gè)大根堆，然后依次取出頂元素（即最大元素），并將剩余元素構(gòu)成新的大根堆，重復(fù)以上過程直到最后一個(gè)元素，就得到了完全排好序的序列。大根堆排序是一種原地排序算法，所以其空間復(fù)雜度為O(1)，只需要常數(shù)級(jí)別的空間；而時(shí)間復(fù)雜度則為O(nlogn)

排序步驟

• 1 構(gòu)建大根堆

我們從序列的最后一個(gè)非葉子節(jié)點(diǎn)開始，依次將其與其子節(jié)點(diǎn)進(jìn)行比較，如果有子節(jié)點(diǎn)比它大，則將它與最大的子節(jié)點(diǎn)交換位置，然后再以交換后的子節(jié)點(diǎn)作為根節(jié)點(diǎn)，繼續(xù)向下比較和交換，直到該節(jié)點(diǎn)成為葉子節(jié)點(diǎn)或者它的子節(jié)點(diǎn)都比它小為止。這樣就可以保證每個(gè)節(jié)點(diǎn)都比其子節(jié)點(diǎn)大，從而構(gòu)建成一個(gè)大根堆。

• 2 取出堆頂元素

由于大根堆的根節(jié)點(diǎn)是最大的元素，因此我們可以直接取出堆頂元素，并將其放到序列的末尾。

• 3 重新構(gòu)建大根堆

取出堆頂元素后，我們需要重新構(gòu)建剩余元素的大根堆。具體操作是將序列的第一個(gè)元素作為根節(jié)點(diǎn)，依次將其與其子節(jié)點(diǎn)進(jìn)行比較，如果有子節(jié)點(diǎn)比它大，則將它與最大的子節(jié)點(diǎn)交換位置，然后再以交換后的子節(jié)點(diǎn)作為根節(jié)點(diǎn)，繼續(xù)向下比較和交換，直到該節(jié)點(diǎn)成為葉子節(jié)點(diǎn)或者它的子節(jié)點(diǎn)都比它小為止。這樣就可以保證剩余元素構(gòu)成一個(gè)新的大根堆。

• 4 重復(fù)執(zhí)行步驟2和步驟3
  重復(fù)執(zhí)行步驟2和步驟3，直到所有元素都被取出，序列就由大到小排好了。

C++代碼實(shí)現(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è)置當(dāng)前節(jié)點(diǎn)arr[" << index << "]=" << arr[index] << "為根節(jié)點(diǎn)" << std::endl;
    int left = 2 * index + 1;
    std::cout << "左節(jié)點(diǎn)索引: " << left << std::endl;
    int right = 2 * index + 2;
    std::cout << "右節(jié)點(diǎn)索引: " << right << std::endl;
    if (left < len) {
        std::cout << "比較左節(jié)點(diǎn)arr[" << left << "]=" << arr[left] << "與根點(diǎn)節(jié)大小" << std::endl;
    } else {
        std::cout << "左節(jié)點(diǎn)超出范圍，即不存在" << std::endl;
    }
    if (left < len && arr[left] > arr[largest])
    {
        largest = left;
    }
   if (right < len) {
        std::cout << "比較右節(jié)點(diǎn)arr[" << right << "]=" << arr[right] << "與根點(diǎn)節(jié)大小" << std::endl;
    } else {
        std::cout << "右節(jié)點(diǎn)超出范圍，即不存在" << std::endl;
    }
    if (right < len && arr[right] > arr[largest])
    {
        largest = right;
    }
    if (largest != index) {
        std::cout << "根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[" << index << "]=" << arr[index] << ")與子(arr[" << largest << "]=" << arr[largest] << ")節(jié)點(diǎn)" << 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)建大根堆， 從最后一個(gè)非葉子節(jié)點(diǎn)向下調(diào)整
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        heapify(arr, len, i);
    }
    std::cout << "大根堆: ";
    printArr(arr);
    // 依次將堆頂元素與堆的最后一個(gè)元素交換，并調(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è)置當(dāng)前節(jié)點(diǎn)arr[4]=23為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 9
右節(jié)點(diǎn)索引: 10
比較左節(jié)點(diǎn)arr[9]=8與根點(diǎn)節(jié)大小
右節(jié)點(diǎn)超出范圍，即不存在
設(shè)置當(dāng)前節(jié)點(diǎn)arr[3]=66為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 7
右節(jié)點(diǎn)索引: 8
比較左節(jié)點(diǎn)arr[7]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[8]=4與根點(diǎn)節(jié)大小
設(shè)置當(dāng)前節(jié)點(diǎn)arr[2]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 5
右節(jié)點(diǎn)索引: 6
比較左節(jié)點(diǎn)arr[5]=5與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[6]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[2]=2)與子(arr[6]=6)節(jié)點(diǎn)
{ 1 39 6 66 23 5 2 9 4 8 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[6]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 13
右節(jié)點(diǎn)索引: 14
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=39為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=66與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=23與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=39)與子(arr[3]=66)節(jié)點(diǎn)
{ 1 66 6 39 23 5 2 9 4 8 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[3]=39為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 7
右節(jié)點(diǎn)索引: 8
比較左節(jié)點(diǎn)arr[7]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[8]=4與根點(diǎn)節(jié)大小
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=66與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=1)與子(arr[1]=66)節(jié)點(diǎn)
{ 66 1 6 39 23 5 2 9 4 8 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=39與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=23與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=1)與子(arr[3]=39)節(jié)點(diǎn)
{ 66 39 6 1 23 5 2 9 4 8 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[3]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 7
右節(jié)點(diǎn)索引: 8
比較左節(jié)點(diǎn)arr[7]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[8]=4與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[3]=1)與子(arr[7]=9)節(jié)點(diǎn)
{ 66 39 6 9 23 5 2 1 4 8 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[7]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 15
右節(jié)點(diǎn)索引: 16
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
大根堆: { 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è)置當(dāng)前節(jié)點(diǎn)arr[0]=8為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=39與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=8)與子(arr[1]=39)節(jié)點(diǎn)
{ 39 8 6 9 23 5 2 1 4 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=8為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=23與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=8)與子(arr[4]=23)節(jié)點(diǎn)
{ 39 23 6 9 8 5 2 1 4 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[4]=8為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 9
右節(jié)點(diǎn)索引: 10
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=39)與最后元素(arr[8]=4)交換
重新設(shè)置大根堆: { 4 23 6 9 8 5 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=4為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=23與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=4)與子(arr[1]=23)節(jié)點(diǎn)
{ 23 4 6 9 8 5 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=4為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=8與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=4)與子(arr[3]=9)節(jié)點(diǎn)
{ 23 9 6 4 8 5 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[3]=4為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 7
右節(jié)點(diǎn)索引: 8
比較左節(jié)點(diǎn)arr[7]=1與根點(diǎn)節(jié)大小
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=23)與最后元素(arr[7]=1)交換
重新設(shè)置大根堆: { 1 9 6 4 8 5 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=9與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=1)與子(arr[1]=9)節(jié)點(diǎn)
{ 9 1 6 4 8 5 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=4與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=8與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=1)與子(arr[4]=8)節(jié)點(diǎn)
{ 9 8 6 4 1 5 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[4]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 9
右節(jié)點(diǎn)索引: 10
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=9)與最后元素(arr[6]=2)交換
重新設(shè)置大根堆: { 2 8 6 4 1 5 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=8與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=2)與子(arr[1]=8)節(jié)點(diǎn)
{ 8 2 6 4 1 5 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
比較左節(jié)點(diǎn)arr[3]=4與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[4]=1與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[1]=2)與子(arr[3]=4)節(jié)點(diǎn)
{ 8 4 6 2 1 5 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[3]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 7
右節(jié)點(diǎn)索引: 8
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=8)與最后元素(arr[5]=5)交換
重新設(shè)置大根堆: { 5 4 6 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=5為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=4與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=6與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=5)與子(arr[2]=6)節(jié)點(diǎn)
{ 6 4 5 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[2]=5為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 5
右節(jié)點(diǎn)索引: 6
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=6)與最后元素(arr[4]=1)交換
重新設(shè)置大根堆: { 1 4 5 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=4與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=5與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=1)與子(arr[2]=5)節(jié)點(diǎn)
{ 5 4 1 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[2]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 5
右節(jié)點(diǎn)索引: 6
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=5)與最后元素(arr[3]=2)交換
重新設(shè)置大根堆: { 2 4 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=4與根點(diǎn)節(jié)大小
比較右節(jié)點(diǎn)arr[2]=1與根點(diǎn)節(jié)大小
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=2)與子(arr[1]=4)節(jié)點(diǎn)
{ 4 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=2為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=4)與最后元素(arr[2]=1)交換
重新設(shè)置大根堆: { 1 2 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
比較左節(jié)點(diǎn)arr[1]=2與根點(diǎn)節(jié)大小
右節(jié)點(diǎn)超出范圍，即不存在
根節(jié)點(diǎn)小于子節(jié)點(diǎn)，交換根(arr[0]=1)與子(arr[1]=2)節(jié)點(diǎn)
{ 2 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[1]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 3
右節(jié)點(diǎn)索引: 4
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
將最大值(arr[0]=2)與最后元素(arr[1]=1)交換
重新設(shè)置大根堆: { 1 }
設(shè)置當(dāng)前節(jié)點(diǎn)arr[0]=1為根節(jié)點(diǎn)
左節(jié)點(diǎn)索引: 1
右節(jié)點(diǎn)索引: 2
左節(jié)點(diǎn)超出范圍，即不存在
右節(jié)點(diǎn)超出范圍，即不存在
排序后: { 1 2 4 5 6 8 9 23 39 66 }

以上就是C++ 大根堆排序?qū)W習(xí)筆記的詳細(xì)內(nèi)容，更多關(guān)于C++ 大根堆排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論