久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

專注電子技術學習與研究
當前位置：單片機教程網 >> MCU設計實例 >> 瀏覽文章

二叉堆的C語言實現

作者:龔平   來源:本站原創   點擊數:…  更新時間：2014年03月14日   【字體：大 中 小】

二叉堆的實現數據結構中如何使用，我任務主要是在操作系統中的任務優先級調度問題，當然也可以用于實現堆排序問題，比如找出數組中的第K個最小值問題，采用二叉堆能夠快速的實現，今天我就采用C語言實現了一個簡單的二叉堆操作，完成這些數據結構我并不知道能干什么，我就當自己在練習C語言的功底吧。逐步完成自己的代碼，希望自己在知識的理解力上有一定的提高。
 
二叉堆是非常有特點的數據結構，可以采用簡單的數組就能實現，當然鏈表的實現也是沒有問題的，畢竟是一個二叉樹問題，當然可以采用鏈表實現。采用數組實現時，可以找到兩個特別明顯的規律：
 
左兒子：L_Son = Parent * 2;
右兒子：R_Son = Parent * 2 + 1;
 
二叉堆是一顆完全填滿的樹，可能例外的是在底層，底層上的元素是從左到右填入，當然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用簡單的基于小值的形式。主要完成的操作：1、最小值的刪除操作，該操作會刪除根節點，然后提升兒子節點來代替根節點，具體的實現過程中通過提升左右兒子中較小的作為父結點，依此提升直到到達最底層，這種實現方式叫做下慮法。2、數據的插入操作，插入操作可能會破壞二叉堆的結構，一般在最底層創建一個空穴，然后比較插入值與空穴父結點的值，如果大于父結點的值，那么直接插入到空穴中，如果小于父結點，則將父結點的值插入到剛創建的空穴中，在父結點所在位置上形成新的父結點，這時候再和父結點的父結點比較，具體操作如上所述，直到找到具體的插入地址。當結點個數為偶數時，在刪除操作中需要注意節點是否有右兒子的情況。具體的可以參考代碼中的說明。
 
具體的實現如下：
結構體：

 

    #ifndef __BINARYHEAP_H_H_
    #define __BINARYHEAP_H_H_

    #include <stdlib.h>
    #include <assert.h>

    #define bool int
    #define true 1
    #define false 0

    /*打算采用數組的方式實現完全二叉堆*/
    typedef struct _binaryheap
    {
            /*因為需要動態擴展，
            *采用靜態數組不方便*/
            int * parray;
            /*目前存在的結點*/
            int currentSize;
            /*樹的實際容量*/
            int capacity;
    }BinaryHeap_t, *BinaryHeap_handle_t;

    #ifdef __cplusplus
    extern "C"
    {
    #endif

    bool init_BinaryHeap(BinaryHeap_handle_t heap, int capacity);
    bool alloc_BinaryHeap(BinaryHeap_handle_t *heap, int capacity);
    void delete_BinaryHeap(BinaryHeap_handle_t heap);
    void free_BinaryHeap(BinaryHeap_handle_t *heap);

    bool insert(BinaryHeap_handle_t heap,int value);
    int deleteMin(BinaryHeap_handle_t heap);
    bool isEmpty(BinaryHeap_handle_t heap);

    #ifdef __cplusplus
    }
    #endif

    #endif

實現的接口函數如下：

 

    #include "binaryheap.h"

    bool isEmpty(BinaryHeap_handle_t heap)
    {
            assert(heap != NULL);
            return heap->currentSize == 0;
    }

    bool init_BinaryHeap(BinaryHeap_handle_t heap, int capacity)
    {
            int *parray = NULL;

            if(heap == NULL)
                    return false;
       
            parray = (int *)calloc(capacity+1,sizeof(int));
            if(parray == NULL)
                    return false;
       
            heap->parray = parray;
            heap->capacity = capacity;
            heap->currentSize = 0;

            return true;
    }

    void delete_BinaryHeap(BinaryHeap_handle_t heap)
    {
            assert(heap != NULL && heap->parray != NULL);

            heap->capacity = 0;
            heap->currentSize = 0;

            free(heap->parray);
            heap->parray = NULL;
    }

    void free_BinaryHeap(BinaryHeap_handle_t *heap)
    {
            assert(*heap != NULL);

            (*heap)->capacity = 0;
            (*heap)->currentSize = 0;

            free((*heap)->parray);
            (*heap)->parray = NULL;

            free(*heap);
            *heap = NULL;
    }

    bool alloc_BinaryHeap(BinaryHeap_handle_t *heap, int capacity)
    {
            int *parray = NULL;

            if(*heap != NULL)
                    return false;

            *heap = (int *)calloc(1, sizeof(BinaryHeap_t));
            if(*heap == NULL)
                    return false;

            /*其中的1，主要是為了使得數組從下標1開始計算*/
            parray =(int *)calloc(capacity + 1, sizeof(int));
            if(parray == NULL)
                    return false;

            (*heap)->parray = parray;
            (*heap)->capacity = capacity;
            (*heap)->currentSize = 0;

            return true;
    }

    /**************************************************
     * 采用上慮法實現數據的插入操作
     * 上慮法的實現方式比較簡單，首先創建一個空節點
     * 然后將需要插入的值與當前空穴的父結點進行比較
     * 如果大于父結點，直接插入空穴中
     * 如果小于父結點的值，則將父結點的值下拉到空穴中
     * 之前父結點的位置就是空穴，接著與上層比較
     * 直到找到父結點大于當前插入值的情況
     **************************************************/
    bool insert(BinaryHeap_handle_t heap, int value)
    {
            int index = 0;

            if(heap == NULL || heap->parray == NULL)
                    return false;

            /*得到一個新的空穴下標*/
            index = ++heap->currentSize;
            /*條件是不是第一個下標和插入值比對應父結點小*/
            while(index > 1 && value < heap->parray[index/2])
            {
                    /*將父結點保存到當前結點處*/
                    heap->parray[index] = heap->parray[index/2];
                    /*得到父結點的空穴位置*/
                    index /= 2;
            }
            /*將插入的值保存到剩余的空穴中*/
            heap->parray[index] = value;

            return true;
    }

    /***********************************************************
     * 下慮法實現數據的重排序操作
     * 實現的方式，將子結點的兩個兒子進行比較，將小的提升
     * 需要注意的是如何讓判斷節點是否一定存在右兒子
     * 實現的方式主要是利用了二叉堆的特性:
     * 2*pare = L_child
     * 2*pare + 1 = R_child;
     ***********************************************************/
    static void presort_BinaryHeap(BinaryHeap_handle_t heap,int hole)
    {
            /*這是二叉堆的特性*/
            int child = hole * 2;
            /*保存當前數據操作*/
            int tmp = 0;

            assert(heap != NULL && heap->parray != NULL);

            tmp = heap->parray[hole];
            /*hold * 2 <= heap->currentSize 判斷了當前結點是否為最低層*/
            for(; hole * 2 <= heap->currentSize; hole = child)
            {
                    child = hole * 2;

                    /*******************************
                    *這句代碼解決是否存在右結點的問題
                    *并確定了那個子結點提升的問題
                    *******************************/
                    if((child != heap->currentSize)
                            && (heap->parray[child + 1] < heap->parray[child]))
                            child ++;

                    if(heap->parray[child] < tmp)
                    {
                            /*將子結點提升為父結點*/
                           heap->parray[hole] = heap->parray[child];
                    }
            }
            /*到達了最低的層，也就是樹葉*/
            heap->parray[hole] = tmp;
    }

    /*實現數據的下慮法實現數據的刪除操作*/
    int deleteMin(BinaryHeap_handle_t heap)
    {
            int ret = 0;
            int index = 0;

            assert(!isEmpty(heap));
            /*需要返回的值*/
            ret = heap->parray[1];

            /*將最后需要釋放內存空間的值保存到第一個內存空間中*/
            heap->parray[1] = heap->parray[heap->currentSize --];
            /*從表頭開始將新的二叉樹進行重新排序*/
            presort_BinaryHeap(heap, 1);

            return ret;
    }

測試代碼：

 

    #include "binaryheap.h"
    #include <stdio.h>
    #include <time.h>

    void print_binaryheap(BinaryHeap_handle_t heap)
    {
            int i = 0;

            assert(heap != NULL && heap->parray != NULL);

            for(i = 1; i <= heap->currentSize; ++ i)
            {
                    if(i %6)
                            printf("%d\t",heap->parray[i]);
                    else
                            printf("\n%d\t",heap->parray[i]);
            }
            printf("\n");
    }

    int main()
    {
            int i = 0;
            int value = 0;

            srand((int)time(0));
            printf("********Test Binaryheap**************\n");

            BinaryHeap_t bheap;
            BinaryHeap_handle_t *pheap = NULL;

            printf("init and alloc test:\n");
            if(init_BinaryHeap(&bheap,10))
           {
                    printf("init_BinaryHeap() successed!\n");
            }
            if (alloc_BinaryHeap(&pheap,15));
            {
                    printf("alloc_BInaryHeap() successed!\n");
            }

            printf("***insert test*****\n");
            for(; i < 10; ++ i)
            {
                    if(!insert(&bheap,5 * i - rand()%20))
                    {
                            printf("i = %d:insert failed !!\n",i);
                    }
            }
            for(i = 0; i < 15; ++ i)
            {
                    if(!insert(pheap,i * 8 - rand()%20))
                    {
                            printf("i = %d:insert failed!!\n",i);
                    }
            }

            print_binaryheap(&bheap);
            print_binaryheap(pheap);

            printf("****deleteMin test****\n");
            for(i = 0; i < 5; ++ i)
            {
                    value = deleteMin(&bheap);
                    printf("bheap deleted:%d\n",value);
                    value = deleteMin(pheap);
                    printf("pheap deleted:%d\n",value);
            }
            print_binaryheap(&bheap);
            print_binaryheap(pheap);

            printf("deleteMin test successed\n");

            printf("****delete and free test:*******\n");
            delete_BinaryHeap(&bheap);

            printf("Is the bheap empty ? %s\n",
                            isEmpty(&bheap)?"Yes":"No");

            free_BinaryHeap(&pheap);

            printf("*********Test successed!***********\n");
            pheap = NULL;
            return 0;
    }

測試結果：

 

    [gong@Gong-Computer c_binaryheap]$ ./testbinaryheap
    ********Test Binaryheap**************
    init and alloc test:
    init_BinaryHeap()
    alloc_BInaryHeap()
    ***insert test*****
    -11    -9    -9    14    15   
    10    21    23    40    26   
    -16    2    14    20    13   
    21    33    49    61    67    76   
    86    83    95    109   
    ****deleteMin test****
    bheap deleted:-11
    pheap deleted:-16
    bheap deleted:-9
    pheap deleted:2
    bheap deleted:-9
    pheap deleted:13
    bheap deleted:10
    pheap deleted:14
    bheap deleted:14
    pheap deleted:20
    15    23    21    40    26   
    21    49    21    61    67   
    76    33    95    83    109   
    deleteMin test successed
    ****delete and free test:*******
    Is the bheap empty ? Yes
    *********Test


從上面的測試結果可知，基本上實現了二叉堆的基本插入、刪除操作。代碼的關鍵點在于刪除中的下慮和插入過程中的上慮操作。以及如何判斷代碼是否存在右兒子，如何充分運用二叉堆的特性。

【關閉窗口】

相關文章

主站蜘蛛池模板： 久久久精品一区二区三区 | 亚洲欧美高清 | 一级aaaaaa毛片免费同男同女 | 亚洲精品乱码久久久久久久久 | 欧美日韩国产一区二区 | 北条麻妃一区二区三区在线观看 | 亚洲国产欧美在线人成 | 青草青草久热精品视频在线观看 | 国产片侵犯亲女视频播放 | 在线视频 亚洲 | 成人免费共享视频 | 成人中文网 | 亚洲免费片 | 亚洲一区二区三区在线免费观看 | 欧美美女一区二区 | 欧美日韩在线一区二区三区 | 男女午夜免费视频 | 久久69精品久久久久久久电影好 | 久在草| 精品日韩一区 | 超碰在线网站 | 日韩午夜精品 | 国产精品99久久久久久动医院 | 亚洲色欧美另类 | 亚洲一二视频 | 欧美一区二区在线视频 | 亚洲福利 | 成人伊人 | 视频一区二区三区中文字幕 | 二区三区av | 久久天天躁狠狠躁夜夜躁2014 | 在线视频亚洲 | 国产成人黄色 | 日韩中文在线观看 | 久久久久久91 | 久婷婷 | 国产精品久久久久久久粉嫩 | 激情欧美日韩一区二区 | 99久久亚洲| 午夜影视| 久久亚洲一区二区 |