欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

【數(shù)據(jù)結構】——堆及其應用

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

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

小堆(大堆)中：任一結點的關鍵碼均小于(大于)等于它的左右孩子的關鍵碼，位于堆頂結點的關鍵碼最小(最大)，從根節(jié)點到每個結點的路徑上數(shù)組元素組成的序列都是遞增(遞減)的堆存儲在下標為0開始的數(shù)組中，因此在堆中給定下標為i的結點時：如果i=0，結點i是根節(jié)點，沒有雙親節(jié)點；否則結點i的雙親結點為結點(i-1)/2如果2 i + 1 <= n - 1，則結點i的左孩子為結點2 i + 1，否則結點i無左孩子如果2 i + 2 <= n - 1，則結點i的右孩子為結點2 i + 2，否則結點i
①大小堆的構建
【數(shù)據(jù)結構】——堆及其應用
將二叉樹調整為最小堆的原理：
從最后一個非葉子結點開始調整，一直到根節(jié)點為止，將每個結點及其子樹調整到滿足小堆的性質即可。
代碼如下：

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

大堆與小堆原理相同，代碼相似，此處不再贅述。
②堆的插入和刪除
插入
其實在一個堆中是可以在任意位置插入和刪除結點的，為了高效起見我們在插入一個結點時我們將該結點尾插到存儲堆結構的順序表中，如果我們插入的結點比原來的大堆中的所有數(shù)據(jù)都大的話我們就破壞了原來的大頂堆的結構了，此時我們就需要調整新堆的，在這里用的是向上調整的算法.
插入數(shù)據(jù)的時間復雜度為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).將最后一個結點的數(shù)據(jù)域與堆頂?shù)脑亟粨Q.
2).刪除最后一個結點，此時刪除的就是原來的堆頂元素
3).向下調整刪除之后的堆，使其繼續(xù)滿足大頂堆的定義.
刪除數(shù)據(jù)的時間復雜度為O(lgn).
插入和刪除的算法會在堆的應用中寫道，此處不再贅述。
堆的應用
①優(yōu)先級隊列
我們知道隊列的特性是先進先出，那什么是優(yōu)先級隊列呢？在某一情況下隊列的先進先出并不能滿足我們的需求，我們需要優(yōu)先級高的先出隊列，這就類似VIP之類的.
下面給出實現(xiàn)優(yōu)先級隊列的兩種思路:
想法一:
Push:在需求的優(yōu)先級的位置插入數(shù)據(jù)，時間復雜度為O(n).
Pop:直接從隊頭刪除數(shù)據(jù)，時間復雜度為O(1).
想法二:
Push:直接插在隊尾，時間復雜度為O(1).
Pop:找到優(yōu)先級最高的元素刪除,時間復雜度為O(n).
在實際應用中第一種想法是優(yōu)于第二種想法的,但是其實還有一種更加高效的方法，那就是用堆實現(xiàn)優(yōu)先級隊列
函數(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;
}

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

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

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

    for (i=k; i<n; i++) //遍歷剩下的數(shù)
    {
        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]交換，然后從堆中去掉這個節(jié)點n，通過減少n的值來實現(xiàn)。剩余的節(jié)點中，新的根節(jié)點可能違背了最大堆的性質，因此需要調用向下調整函數(shù)來維護最大堆。

函數(shù)代碼：

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

//優(yōu)先級隊列問題
#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)  //交換函數(shù)
{
    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問題測試時要巧妙構建測試案例。

網(wǎng)站名稱：【數(shù)據(jù)結構】——堆及其應用
URL地址：http://chinadenli.net/article2/gsjcoc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、網(wǎng)站導航、定制網(wǎng)站、云服務器、用戶體驗、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站優(yōu)化排名