二叉堆的實現數據結構中如何使用，我任務主要是在操作系統中的任務優先級調度問題，當然也可以用于實現堆排序問題，比如找出數組中的第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）[nettpage]

    {

    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

    從上面的測試結果可知，基本上實現了二叉堆的基本插入、刪除操作。代碼的關鍵點在于刪除中的下慮和插入過程中的上慮操作。以及如何判斷代碼是否存在右兒子，如何充分運用二叉堆的特性。    二叉堆的實現數據結構中如何使用，我任務主要是在操作系統中的任務優先級調度問題，當然也可以用于實現堆排序問題，比如找出數組中的第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;

    }

    /***********************************************************

    * 下慮法實現數據的重排序操作

    * 實現的方式，將子結點的兩個兒子進行比較tbw，將小的提升

    * 需要注意的是如何讓判斷節點是否一定存在右兒子

    * 實現的方式主要是利用了二叉堆的特性：

    * 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

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