最小堆和最小堆排序

1、原理介紹：百度百科

2、最小堆的構造和添加

#include <stdio.h>
#define N 9 // 最小堆得元素個數

int minHeap[N]; // 存放最小堆的數組
int index1 = ; // 最小堆數組索引

void add(int d) // 向最小堆内添加資料
{
    if(index1 >= N)
    {
        printf("Out of range!\n");
        return;
    }
    int t = index1; // t指向存放位置
    int pt = (t - ) / ; // 父節點
    while(t > ) // t指向0位置時結束循環
    {
        if(minHeap[pt] > d) // 當父節點資料比插入資料大時，将父節點資料下移
        {
            minHeap[t] = minHeap[pt];
            t = pt;
            pt = (t - ) / ;
        }
        else // 找到合适位置
            break;
    }
    minHeap[t] = d; // 最後存放資料位置
    index1++;
}
int main()
{
    int t[] = {, , , , , , , , };
    int i;
    for(i=; i<; i++)
    {
        add(t[i]);
    }

    for(i=; i<; i++) // 輸出測試
    {
        printf("%d ", minHeap[i]);
    }
    printf("\n");
    return ;
}
           

3、最小堆排序算法

在構造最小堆時，沒有必要一個節點一個節點的添加，可以将原來的數組看成一顆完全二叉樹。并且知道數組元素個數。那麼從最後一個非葉子節點的節點開始逐漸向前，直到第一個節點。對每個節點與它的最小孩子節點比較，如果大于最小孩子節點，那麼将孩子節點上移，該節點下移。直到找到不大于孩子節點的位置或者到孩子節點。将該節點值儲存。

排序思想：

a. 使用變量index1=n-1。

b. 數組長度為n，循環n-1次。

c. 每次循環，構造(調整)一次最小堆，此時注意調整的數組長度為index1+1。排好序的元素不再調整。

d. 交換第一個元素和第index1個元素，index1–。(較小元素放到後面)

e. 直到循環結束，輸出排序結果。

void outputt(int t[], int len) // 數組輸出
{
    int i;
    for(i=; i<len-; i++) // 輸出測試
    {
        printf("%d ", t[i]);
    }
    printf("%d\n", t[i]);
}

void heap(int t[], int len) // 調整二叉樹生成堆
{
    int i;
    int l, r;
    int min, u;
    int ti, values;
    for(i=len/-; i>=; i--) // 數組下标從0開始
    {
        ti = i; // 指向i元素存放位置
        values = t[i];
        while(ti < len)
        {
            l =  * ti + ;
            r = l + ;
            u = -;

            if(l < len) // 取孩子中最小者最小
            {
                min = t[l];
                u = l;
            }
            if(r < len && t[r] < min)
            {
                min = t[r];
                u = r;
            }

            if(u == -) // 到達葉子節點
                break;

            if(values > min)
            {
                t[ti] = min;
                ti = u;
            }
            else // 不大于孩子節點
                break;
        }
        t[ti] = values; // 存放該值
    }
}

void heapSort(int t[], int len) // 進行堆排序
{
    int tmp;
    int index1 = len - ;
    while(index1 > ) // 當未排序的隻剩一個時，沒必要再排
    {
        heap(t, index1 + ); // 構造或調整最小堆
        tmp = t[];
        t[] = t[index1];
        t[index1] = tmp;
        outputt(t, ); // 檢視排序過程
        index1--;
    }
}
           

4、最小堆删除元素。每次删除第一個元素，并且把最後一個元素拿過來補充第一個元素，然後對這個新的二叉樹進行調整使其滿足最小堆的條件，不過此時調整僅從根節點調整即可。其實第三部分的堆排序中，隻有第一次需要從最後一個非葉子節點進行調整，其他情況從根節點調整即可。最大堆的使用在最小堆的某些判斷條件處更改即可。