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

来源:https://www.cnblogs.com/zhonglongbo/archive/2018/02/25/8470553.html
-Advertisement-
Play Games

本文詳細闡述了大小堆的創建，堆的插入和刪除；為了加深記憶還用堆實現了優先順序隊列問題，topk問題，堆排序問題（包含原理，思路，代碼實現，以及測試用例）。本文在windows平臺下vs2008上採用C語言實現。 ...


一、堆
先說說堆概念：如果有一個關鍵碼的集合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問題測試時要巧妙構建測試案例。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Mina 組件介紹之 IoAcceptor 與 IoConnector
    在網路通信中，Socket通信的雙方分為服務端與客戶端，在Java NIO 的實現中採用Socket/ServerSocket, SocketChannel/ServerSocketChannel分別表示客戶端與服務端對象及程式與所操作的Socket間的連接通道。 在Mina框架中採用IoAccep ...
  • Java面試題庫及答案解析
    1、面向對象編程（OOP）有哪些優點？ 代碼開發模塊化，更易維護和修改。 代碼復用。 增強代碼的可靠性和靈活性。 增加代碼的可理解性。 2、面向對象編程有哪些特性？ 封裝、繼承、多態、抽象 封裝 封裝給對象提供了隱藏內部特性和行為的能力。對象提供一些能被其他對象訪問的方法來改變它內部的數據。在Jav ...
  • C++中如何按照map中的value來進行排序
    sort函數無法對map進行排序，網上的方法一般是通過將map轉為vector後，再來使用sort進行排序。 如下， 比較函數 主函數 ...
  • 博弈總結
    SG函數部分內容大多借(chao)鑒(xi)自 "zyf學長" 也有一些自己獨到的理解 Hackenbush和納什均衡直接棄掉了 不平等博弈有空再看 題目還有很多沒切完 不過確實是沒時間了，畢竟博弈只是一小塊內容。 經典博弈 "博弈論入門之巴什博奕" "博弈論入門之nim游戲" "博弈論入門之威佐夫 ...
  • python 3.x 學習筆記15(多線程)
    1.線程進程進程：程式並不能單獨運行，只有將程式裝載到記憶體中，系統為它分配資源才能運行，而這種執行的程式就稱之為進程，不具備執行感念，只是程式各種資源集合 線程：線程是操作系統能夠進行運算調度的最小單位。它被包含在進程之中，是進程中的實際運作單位。一條線程指的是進程中一個單一順序的控制流，一個進程中 ...
  • gradle構建工具入門
    實際設置：系統變數新建： PATH新加： 查看是否安裝成功： ...
  • 【JavaWeb】客戶關係管理系統
    前言 為了鞏固開發的流程，我們再拿一個客戶關係管理系統來練手...！ 成果圖 我們完成的就是下麵的項目！ 搭建配置環境 配置Tomcat 導入開發包 建立開發用到的程式包 在資料庫創建相對應的表 開發實體 開發實體十分簡單，對照著資料庫的表就行了！ 開發獲取資料庫連接池的Utils 導入配置文件 開 ...
  • 博弈論進階之樹的刪邊游戲與無向圖的刪邊游戲
    PS:本文內容大部分借(chao)鑒(xo)自 "yhqz" 樹的刪邊游戲 給出一個有 N個點的樹，有一個點作為樹的根節點。游戲者輪流從樹中刪去邊，刪去一條邊後，不與根節點相連的部分將被移走。誰無法移動誰輸。 結論 葉子節點的SG值為0；中間節點的SG值為它的所有子節點的SG值加1後的異或和。 證明 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類