快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)之堆排序詳解

更新時(shí)間：2022年03月10日 11:21:39 作者：清歡有道

堆是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個(gè)可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。本文將通過圖片詳細(xì)介紹堆排序，需要的可以參考一下

1.堆的概念及結(jié)構(gòu)

如果有一個(gè)關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹（二叉樹具體概念參見——二叉樹詳解）的順序存儲方式存儲在一個(gè)一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。

2.堆的實(shí)現(xiàn)

堆的實(shí)現(xiàn)請參見——二叉樹詳解（堆的實(shí)現(xiàn)）

2.1 堆的向下調(diào)整算法

（此文章都已建小堆為例）

向下調(diào)整算法前提：當(dāng)前樹左右子樹都是小堆

核心思想：選出左右孩子中小的那個(gè)，和父親交換，小的往上浮，大的往下沉，這里是小堆，如果是大堆則相反。

代碼實(shí)現(xiàn)

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
//堆向下調(diào)整算法
void AdjustDown(int *a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        //保證孩子節(jié)點(diǎn)child為兩個(gè)孩子中的最小值；保證不越界
        if (a[child] > a[child + 1] && child+1 < n)
            ++child;
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}

2.2 堆的向上調(diào)整算法

使用場景：向上調(diào)整算法適用于向堆中插入數(shù)據(jù)，當(dāng)向堆中插入數(shù)據(jù)就可能會導(dǎo)致堆失去大堆或者小堆的性質(zhì)，此時(shí)需要重新調(diào)整，向上調(diào)整的思路與向下調(diào)整算法的思路類似，向上調(diào)整算法只需要從插入結(jié)點(diǎn)位置開始和父節(jié)點(diǎn)比較。

圖示：

代碼實(shí)現(xiàn)：

void AdjustUp(int *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] > a[child])
        {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

2.3 建堆（數(shù)組）

從最后一個(gè)非葉子節(jié)點(diǎn)位置行依次開始調(diào)整，如圖：

代碼實(shí)現(xiàn)：

int parent = (n-2) / 2;
    //首先對每一個(gè)非葉子節(jié)點(diǎn)進(jìn)行一次向下調(diào)整算法，保證每個(gè)非葉子節(jié)點(diǎn)的
    //孩子都小于它的父節(jié)點(diǎn)，然后可得到最小值，就在堆的頂端的父節(jié)點(diǎn)（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }

2.4 堆排序

升序建大堆，降序建小堆

void HeapSort(int *a, int n)
{
    int parent = (n-2) / 2;
    //首先對每一個(gè)非葉子節(jié)點(diǎn)進(jìn)行一次向下調(diào)整算法，保證每個(gè)非葉子節(jié)點(diǎn)的
    //孩子都小于它的父節(jié)點(diǎn)，然后可得到最小值，就在堆的頂端的父節(jié)點(diǎn)（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }
    int end = n-1;
    while (end>0)
    {
        //將堆頂?shù)臄?shù)與最后的end,以此循環(huán)，進(jìn)行交換就可得到有序序列
        //注意：建小堆，得到降序序列
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        --end;
    }
}