【數據結構】——堆及其應用

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

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

將二叉樹調整為最小堆的原理：
從最后一個非葉子結點開始調整，一直到根節點為止，將每個結點及其子樹調整到滿足小堆的性質即可。
代碼如下：

void AdjustDown(DataType* a, size_t n, int root) //向下調整
{
    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]<a[parent])
            Swap(&a[child],&a[parent]);
        else
            break;

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

大堆與小堆原理相同，代碼相似，此處不再贅述。
②堆的插入和刪除
插入
其實在一個堆中是可以在任意位置插入和刪除結點的，為了高效起見我們在插入一個結點時我們將該結點尾插到存儲堆結構的順序表中，如果我們插入的結點比原來的大堆中的所有數據都大的話我們就破壞了原來的大頂堆的結構了，此時我們就需要調整新堆的，在這里用的是向上調整的算法.
插入數據的時間復雜度為O(lgn).
向上調整代碼：

void AdjustUp(DataType* a,int child) //向上調整
{
    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).將最后一個結點的數據域與堆頂的元素交換.
2).刪除最后一個結點，此時刪除的就是原來的堆頂元素
3).向下調整刪除之后的堆，使其繼續滿足大頂堆的定義.
刪除數據的時間復雜度為O(lgn).
插入和刪除的算法會在堆的應用中寫道，此處不再贅述。
堆的應用
①優先級隊列
我們知道隊列的特性是先進先出，那什么是優先級隊列呢？在某一情況下隊列的先進先出并不能滿足我們的需求，我們需要優先級高的先出隊列，這就類似VIP之類的.
下面給出實現優先級隊列的兩種思路:
想法一:
Push:在需求的優先級的位置插入數據，時間復雜度為O(n).
Pop:直接從隊頭刪除數據，時間復雜度為O(1).
想法二:
Push:直接插在隊尾，時間復雜度為O(1).
Pop:找到優先級最高的元素刪除,時間復雜度為O(n).
在實際應用中第一種想法是優于第二種想法的,但是其實還有一種更加高效的方法，那就是用堆實現優先級隊列
函數代碼：

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;
}

頭文件和測試代碼在結尾給出。
②topk問題（構建相反堆找出前k個數） 在大規模數據處理中，經常會遇到的一類問題：在海量數據中找出出現頻率最好的前k個數，或者從海量數據中找出最大的前k個數，這類問題通常被稱為top K問題。例如，在搜索引擎中，統計搜索最熱門的10個查詢詞；在歌曲庫中統計下載最高的前10首歌等。

維護一個K個數據的小頂堆，遍歷元素，若元素大于堆頂元素，則將堆頂元素移除，當前元素插入堆頂，并進行調整。
代碼實現

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

    for (i=k; i<n; i++) //遍歷剩下的數
    {
        if (a[i]>a[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);//向下調整
        }
    }

    for (i=0; i<k; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

頭文件和測試代碼在結尾給出。
③堆排序（升序 — 構建大堆 降序 — 構建小堆）
堆排序：先建立一個最大堆。然后將最大堆的a[0]與a[n]交換，然后從堆中去掉這個節點n，通過減少n的值來實現。剩余的節點中，新的根節點可能違背了最大堆的性質，因此需要調用向下調整函數來維護最大堆。

函數代碼：

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

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

}

頭文件和測試代碼在結尾給出。

Head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include<string.h>

typedef int DataType; 

//構建大小堆
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);

//優先級隊列問題
#define N 1000 

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

}PriorityQueue; 

void PriorityQueueInit(PriorityQueue* q);  //初始化
void PriorityQueuePush(PriorityQueue* q, DataType x); //入隊
void PriorityQueuePop(PriorityQueue* q); //出隊
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)  //交換函數
{
    int tmp = *child;
    *child = *parent;
    *parent = tmp;
}

void AdjustDown(DataType* a, size_t n, int root) //向下調整
{
    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]>a[parent])
            Swap(&a[child],&a[parent]);
        else
            break;

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

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

void AdjustUp(DataType* a,int child) //向上調整
{
    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問題
{
    size_t i = k;
    MakeSmallHeap(a,k);

    for (i=k; i<n; i++)
    {
        if (a[i]>a[0])
        {
            a[0] = a[i];
            AdjustDown(a,k,0);
        }
    }

    for (i=0; i<k; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

void PriorityQueueInit(PriorityQueue* q)
{
    assert(q);
    memset(q->_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問題測試時要巧妙構建測試案例。