一、堆
先說(shuō)說(shuō)堆概念：如果有一個(gè)關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >=K2i+1 且 Ki >= K2i+2) i =0，1，2…，則稱為小堆(或大堆)。

山南網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),山南網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為山南1000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的山南做網(wǎng)站的公司定做！

小堆(大堆)中：任一結(jié)點(diǎn)的關(guān)鍵碼均小于(大于)等于它的左右孩子的關(guān)鍵碼，位于堆頂結(jié)點(diǎn)的關(guān)鍵碼最小(最大)，從根節(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑上數(shù)組元素組成的序列都是遞增(遞減)的堆存儲(chǔ)在下標(biāo)為0開(kāi)始的數(shù)組中，因此在堆中給定下標(biāo)為i的結(jié)點(diǎn)時(shí)：如果i=0，結(jié)點(diǎn)i是根節(jié)點(diǎn)，沒(méi)有雙親節(jié)點(diǎn)；否則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為結(jié)點(diǎn)(i-1)/2如果2 i + 1 <= n - 1，則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2 i + 1，否則結(jié)點(diǎn)i無(wú)左孩子如果2 i + 2 <= n - 1，則結(jié)點(diǎn)i的右孩子為結(jié)點(diǎn)2 i + 2，否則結(jié)點(diǎn)i
①大小堆的構(gòu)建

將二叉樹(shù)調(diào)整為最小堆的原理：
從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始調(diào)整，一直到根節(jié)點(diǎn)為止，將每個(gè)結(jié)點(diǎn)及其子樹(shù)調(diào)整到滿足小堆的性質(zhì)即可。
代碼如下：

void AdjustDown(DataType* a, size_t n, int root) //向下調(diào)整
{
    int parent = root;
    int child = parent*2 + 1;
    while (child<(int)n)
    {
        if(a[child]>a[child+1] && child+1 <(int)n)
            ++child;

        if (a[child]>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

大堆與小堆原理相同，代碼相似，此處不再贅述。
②堆的插入和刪除
插入
其實(shí)在一個(gè)堆中是可以在任意位置插入和刪除結(jié)點(diǎn)的，為了高效起見(jiàn)我們?cè)诓迦胍粋€(gè)結(jié)點(diǎn)時(shí)我們將該結(jié)點(diǎn)尾插到存儲(chǔ)堆結(jié)構(gòu)的順序表中，如果我們插入的結(jié)點(diǎn)比原來(lái)的大堆中的所有數(shù)據(jù)都大的話我們就破壞了原來(lái)的大頂堆的結(jié)構(gòu)了，此時(shí)我們就需要調(diào)整新堆的，在這里用的是向上調(diào)整的算法.
插入數(shù)據(jù)的時(shí)間復(fù)雜度為O(lgn).
向上調(diào)整代碼：

void AdjustUp(DataType* a,int child) //向上調(diào)整
{
    int parent = (child-1)>>1;
    while (child >0)
    {
        if (a[parent] > a[child] && parent >= 0)
            Swap(&a[child],&a[parent]);
        else
            break;

        child = parent;
        parent = (child-1)>>1;
    }
}

刪除
1).將最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域與堆頂?shù)脑亟粨Q.
2).刪除最后一個(gè)結(jié)點(diǎn)，此時(shí)刪除的就是原來(lái)的堆頂元素
3).向下調(diào)整刪除之后的堆，使其繼續(xù)滿足大頂堆的定義.
刪除數(shù)據(jù)的時(shí)間復(fù)雜度為O(lgn).
插入和刪除的算法會(huì)在堆的應(yīng)用中寫道，此處不再贅述。
堆的應(yīng)用
①優(yōu)先級(jí)隊(duì)列
我們知道隊(duì)列的特性是先進(jìn)先出，那什么是優(yōu)先級(jí)隊(duì)列呢？在某一情況下隊(duì)列的先進(jìn)先出并不能滿足我們的需求，我們需要優(yōu)先級(jí)高的先出隊(duì)列，這就類似VIP之類的.
下面給出實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的兩種思路:
想法一:
Push:在需求的優(yōu)先級(jí)的位置插入數(shù)據(jù)，時(shí)間復(fù)雜度為O(n).
Pop:直接從隊(duì)頭刪除數(shù)據(jù)，時(shí)間復(fù)雜度為O(1).
想法二:
Push:直接插在隊(duì)尾，時(shí)間復(fù)雜度為O(1).
Pop:找到優(yōu)先級(jí)最高的元素刪除,時(shí)間復(fù)雜度為O(n).
在實(shí)際應(yīng)用中第一種想法是優(yōu)于第二種想法的,但是其實(shí)還有一種更加高效的方法，那就是用堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列
函數(shù)代碼：

void PriorityQueuePush(PriorityQueue* q, DataType x)
{
    assert(q);
    if (q->_size == N)
        return;

    q->_a[q->_size] = x;
    q->_size++;

    AdjustUp(q->_a,q->_size-1);
}

void PriorityQueuePop(PriorityQueue* q)
{
    assert(q);
    if (q->_size == 0)
        return;

    q->_a[0] = q->_a[q->_size-1];
    q->_size--;

    AdjustDown(q->_a,q->_size,0);
}

DataType PriorityQueueTop(PriorityQueue* q)
{
    if (PriorityQueueEmpty(q))
        return q->_a[0];
}

size_t PriorityQueueSize(PriorityQueue* q)
{
    assert(q);
    return q->_size;
}

size_t PriorityQueueEmpty(PriorityQueue* q) 
{
    assert(q);
    if (q->_size > 0)
        return 1;
    else
        return 0;
}

頭文件和測(cè)試代碼在結(jié)尾給出。
②topk問(wèn)題（構(gòu)建相反堆找出前k個(gè)數(shù)）在大規(guī)模數(shù)據(jù)處理中，經(jīng)常會(huì)遇到的一類問(wèn)題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)，這類問(wèn)題通常被稱為top K問(wèn)題。例如，在搜索引擎中，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢?cè)~；在歌曲庫(kù)中統(tǒng)計(jì)下載最高的前10首歌等。

維護(hù)一個(gè)K個(gè)數(shù)據(jù)的小頂堆，遍歷元素，若元素大于堆頂元素，則將堆頂元素移除，當(dāng)前元素插入堆頂，并進(jìn)行調(diào)整。
代碼實(shí)現(xiàn)

void TopK(DataType* a, size_t n, size_t k) //topk問(wèn)題
{
    size_t i = k;
    MakeSmallHeap(a,k); //構(gòu)建小堆

    for (i=k; ia[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);//向下調(diào)整
        }
    }

    for (i=0; i

頭文件和測(cè)試代碼在結(jié)尾給出。
③堆排序（升序 — 構(gòu)建大堆 降序 — 構(gòu)建小堆）
堆排序：先建立一個(gè)最大堆。然后將最大堆的a[0]與a[n]交換，然后從堆中去掉這個(gè)節(jié)點(diǎn)n，通過(guò)減少n的值來(lái)實(shí)現(xiàn)。剩余的節(jié)點(diǎn)中，新的根節(jié)點(diǎn)可能違背了最大堆的性質(zhì)，因此需要調(diào)用向下調(diào)整函數(shù)來(lái)維護(hù)最大堆。

函數(shù)代碼：

void HeapSort(DataType* a, size_t n)  //堆排序
{
    MakeBigHeap(a,n); //構(gòu)建大堆

    while (n>0)
    {
        Swap(&a[0],&a[n-1]);
        n--;
        AdjustDown(a,n,0);
    }

}

頭文件和測(cè)試代碼在結(jié)尾給出。

Head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include 
#include 
#include 
#include 
#include

typedef int DataType; 

//構(gòu)建大小堆
void AdjustDown(DataType* a, size_t n, int root);
void MakeBigHeap(DataType* a, size_t n);
void MakeSmallHeap(DataType* a, size_t n);
void AdjustUp(DataType* a,int child);

// topk 最大的前K 
void TopK(DataType* a, size_t n, size_t k);

//優(yōu)先級(jí)隊(duì)列問(wèn)題
#define N 1000 

typedef struct PriorityQueue 
{ 
    DataType _a[N]; 
    size_t _size; 

}PriorityQueue; 

void PriorityQueueInit(PriorityQueue* q);  //初始化
void PriorityQueuePush(PriorityQueue* q, DataType x); //入隊(duì)
void PriorityQueuePop(PriorityQueue* q); //出隊(duì)
DataType PriorityQueueTop(PriorityQueue* q); 
size_t PriorityQueueSize(PriorityQueue* q); 
size_t PriorityQueueEmpty(PriorityQueue* q); 

void HeapSort(DataType* a, size_t n); //堆排序

#endif //__HEAD_H__

Head.c

#include "Heap.h"

static void Swap(int *child,int *parent)  //交換函數(shù)
{
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

void AdjustDown(DataType* a, size_t n, int root) //向下調(diào)整
{
    int parent = root;
    int child = parent*2 + 1;
    while (child<(int)n)
    {
        if(a[child]a[parent])
            Swap(&a[child],&a[parent]);
        else
            break;

        parent = child;
        child = parent*2 + 1;
    }
}
void MakeBigHeap(DataType* a, size_t n) //構(gòu)建大堆
{
    int i = (n-2)>>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

void MakeSmallHeap(DataType* a, size_t n) //構(gòu)建小堆
{
    int i = (n-2)>>1;
    for (; i >= 0; --i)
    {
        AdjustDown(a,n,i);
    }
}

void AdjustUp(DataType* a,int child) //向上調(diào)整
{
    int parent = (child-1)>>1;
    while (child >0)
    {
        if (a[parent] > a[child] && parent >= 0)
            Swap(&a[child],&a[parent]);
        else
            break;

        child = parent;
        parent = (child-1)>>1;
    }
}

void TopK(DataType* a, size_t n, size_t k) //topk問(wèn)題
{
    size_t i = k;
    MakeSmallHeap(a,k);

    for (i=k; ia[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);
        }
    }

    for (i=0; i_a,0,sizeof(DataType)*N);
    q->_size = 0;
}

void PriorityQueuePush(PriorityQueue* q, DataType x)
{
    assert(q);
    if (q->_size == N)
        return;

    q->_a[q->_size] = x;
    q->_size++;

    AdjustUp(q->_a,q->_size-1);
}

void PriorityQueuePop(PriorityQueue* q)
{
    assert(q);
    if (q->_size == 0)
        return;

    q->_a[0] = q->_a[q->_size-1];
    q->_size--;

    AdjustDown(q->_a,q->_size,0);
}

DataType PriorityQueueTop(PriorityQueue* q)
{
    if (PriorityQueueEmpty(q))
        return q->_a[0];
}

size_t PriorityQueueSize(PriorityQueue* q)
{
    assert(q);
    return q->_size;
}

size_t PriorityQueueEmpty(PriorityQueue* q) 
{
    assert(q);
    if (q->_size > 0)
        return 1;
    else
        return 0;
}

void HeapSort(DataType* a, size_t n)  //堆排序
{
    MakeBigHeap(a,n);

    while (n>0)
    {
        Swap(&a[0],&a[n-1]);
        n--;
        AdjustDown(a,n,0);
    }

}

Test.c

#include "Heap.h"

void Test1()
{ 
    int  i = 0;
    DataType a[] = {16, 18, 15, 17, 14, 19,10,11, 13, 12};
    MakeSmallHeap(a, sizeof(a)/sizeof(DataType));
    MakeBigHeap(a, sizeof(a)/sizeof(DataType)); 

    DataType NArray[1000]; 
    srand((int)time(0)); 
    for (i = 0; i < 1000; ++i) 
    { 
        NArray[i] = rand()%10000; 
    } 

    NArray[30] = 10001; 
    NArray[350] = 10002; 
    NArray[999] = 10003; 
    NArray[158] = 10004; 
    NArray[334] = 10005; 

    TopK(NArray, 1000, 5); 

    HeapSort(a,sizeof(a)/sizeof(DataType));
}

void TestPriorityQueue() 
{ 
    PriorityQueue q; 
    PriorityQueueInit(&q); 
    PriorityQueuePush(&q, 5); 
    PriorityQueuePush(&q, 2); 
    PriorityQueuePush(&q, 3); 
    PriorityQueuePush(&q, 7); 
    PriorityQueuePush(&q, 6); 
    PriorityQueuePush(&q, 1); 
    PriorityQueuePush(&q, 4); 

    while (PriorityQueueEmpty(&q) != 0) 
    { 
        printf("%d ", PriorityQueueTop(&q)); 
        PriorityQueuePop(&q); 
    } 
    printf("\n"); 

} 

int main()
{
    Test1();
    TestPriorityQueue();
    return 0;
}

topk問(wèn)題測(cè)試時(shí)要巧妙構(gòu)建測(cè)試案例。