二叉堆的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中如何使用，我任務主要是在操作系統(tǒng)中的任務優(yōu)先級調(diào)度問題，當然也可以用于實現(xiàn)堆排序問題，比如找出數(shù)組中的第K個最小值問題，采用二叉堆能夠快速的實現(xiàn)，今天我就采用C語言實現(xiàn)了一個簡單的二叉堆操作，完成這些數(shù)據(jù)結(jié)構(gòu)我并不知道能干什么，我就當自己在練習C語言的功底吧。逐步完成自己的代碼，希望自己在知識的理解力上有一定的提高。
二叉堆是非常有特點的數(shù)據(jù)結(jié)構(gòu)，可以采用簡單的數(shù)組就能實現(xiàn)，當然鏈表的實現(xiàn)也是沒有問題的，畢竟是一個二叉樹問題，當然可以采用鏈表實現(xiàn)。采用數(shù)組實現(xiàn)時，可以找到兩個特別明顯的規(guī)律：
左兒子：L_Son = Parent * 2;
右兒子：R_Son = Parent * 2 + 1;
二叉堆是一顆完全填滿的樹，可能例外的是在底層，底層上的元素是從左到右填入，當然二叉堆可以是基于大值的排序，也可以是基于小值的排列形式，本文采用簡單的基于小值的形式。主要完成的操作：1、最小值的刪除操作，該操作會刪除根節(jié)點，然后提升兒子節(jié)點來代替根節(jié)點，具體的實現(xiàn)過程中通過提升左右兒子中較小的作為父結(jié)點，依此提升直到到達最底層，這種實現(xiàn)方式叫做下慮法。2、數(shù)據(jù)的插入操作，插入操作可能會破壞二叉堆的結(jié)構(gòu)，一般在最底層創(chuàng)建一個空穴，然后比較插入值與空穴父結(jié)點的值，如果大于父結(jié)點的值，那么直接插入到空穴中，如果小于父結(jié)點，則將父結(jié)點的值插入到剛創(chuàng)建的空穴中，在父結(jié)點所在位置上形成新的父結(jié)點，這時候再和父結(jié)點的父結(jié)點比較，具體操作如上所述，直到找到具體的插入地址。當結(jié)點個數(shù)為偶數(shù)時，在刪除操作中需要注意節(jié)點是否有右兒子的情況。具體的可以參考代碼中的說明。
具體的實現(xiàn)如下：
結(jié)構(gòu)體：
#ifndef __BINARYHEAP_H_H_
#define __BINARYHEAP_H_H_
#include <stdlib.h>
#include <assert.h>
#define bool int
#define true 1
#define false 0
/*打算采用數(shù)組的方式實現(xiàn)完全二叉堆*/
typedef struct _binaryheap
{
/*因為需要動態(tài)擴展，
*采用靜態(tài)數(shù)組不方便*/
int * parray;
/*目前存在的結(jié)點*/
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
實現(xiàn)的接口函數(shù)如下：
#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，主要是為了使得數(shù)組從下標1開始計算*/
parray =(int *)calloc(capacity + 1, sizeof(int));
if(parray == NULL)
return false;
(*heap)->parray = parray;
(*heap)->capacity = capacity;
(*heap)->currentSize = 0;
return true;
}
/**************************************************
* 采用上慮法實現(xiàn)數(shù)據(jù)的插入操作
* 上慮法的實現(xiàn)方式比較簡單，首先創(chuàng)建一個空節(jié)點
* 然后將需要插入的值與當前空穴的父結(jié)點進行比較
* 如果大于父結(jié)點，直接插入空穴中
* 如果小于父結(jié)點的值，則將父結(jié)點的值下拉到空穴中
* 之前父結(jié)點的位置就是空穴，接著與上層比較
* 直到找到父結(jié)點大于當前插入值的情況
**************************************************/
bool insert(BinaryHeap_handle_t heap, int value)
{
int index = 0;
if(heap == NULL || heap->parray == NULL)
return false;
/*得到一個新的空穴下標*/
index = ++heap->currentSize;
/*條件是不是第一個下標和插入值比對應父結(jié)點小*/
while(index > 1 && value < heap->parray[index/2])
{
/*將父結(jié)點保存到當前結(jié)點處*/
heap->parray[index] = heap->parray[index/2];
/*得到父結(jié)點的空穴位置*/
index /= 2;
}
/*將插入的值保存到剩余的空穴中*/
heap->parray[index] = value;
return true;
}
/***********************************************************
* 下慮法實現(xiàn)數(shù)據(jù)的重排序操作
* 實現(xiàn)的方式，將子結(jié)點的兩個兒子進行比較，將小的提升
* 需要注意的是如何讓判斷節(jié)點是否一定存在右兒子
* 實現(xiàn)的方式主要是利用了二叉堆的特性:
* 2*pare = L_child
* 2*pare + 1 = R_child;
***********************************************************/
static void presort_BinaryHeap(BinaryHeap_handle_t heap,int hole)
{
/*這是二叉堆的特性*/
int child = hole * 2;
/*保存當前數(shù)據(jù)操作*/
int tmp = 0;
assert(heap != NULL && heap->parray != NULL);
tmp = heap->parray[hole];
/*hold * 2 <= heap->currentSize 判斷了當前結(jié)點是否為最低層*/
for(; hole * 2 <= heap->currentSize; hole = child)
{
child = hole * 2;
/*******************************
*這句代碼解決是否存在右結(jié)點的問題
*并確定了那個子結(jié)點提升的問題
*******************************/
if((child != heap->currentSize)
&& (heap->parray[child + 1] < heap->parray[child]))
child ++;
if(heap->parray[child] < tmp)
{
/*將子結(jié)點提升為父結(jié)點*/
heap->parray[hole] = heap->parray[child];
}
}
/*到達了最低的層，也就是樹葉*/
heap->parray[hole] = tmp;
}
/*實現(xiàn)數(shù)據(jù)的下慮法實現(xiàn)數(shù)據(jù)的刪除操作*/
int deleteMin(BinaryHeap_handle_t heap)
{
int ret = 0;
int index = 0;
assert(!isEmpty(heap));
/*需要返回的值*/
ret = heap->parray[1];
/*將最后需要釋放內(nèi)存空間的值保存到第一個內(nèi)存空間中*/
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;
}
測試結(jié)果：
[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
從上面的測試結(jié)果可知，基本上實現(xiàn)了二叉堆的基本插入、刪除操作。代碼的關(guān)鍵點在于刪除中的下慮和插入過程中的上慮操作。以及如何判斷代碼是否存在右兒子，如何充分運用二叉堆的特性。