堆的动态创建与根节点删除

堆的介绍与调整

关于堆的介绍以及对于给定的完全二叉树，调整为大根堆或者小根堆，可以参考博文http://blog.****.net/pngynghay/article/details/22052737，在此不再赘述。

本文主要是实现动态的创建一个堆，并且动态地向堆中插入元素，以及删除堆顶元素。

堆的创建与删除操作分为大根堆与小根堆两种实现。

头文件

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>

数据结构

typedef struct
{
	uint32_t cursize;
	uint32_t maxsize;
	uint32_t *element;        
}heap_t;

typedef enum
{
	false,
	true
}bool;

公共方法

/*申请堆，入参为堆中元素的个数*/
heap_t *heap_malloc(uint32_t size)
{
	heap_t * heap = NULL;
	uint32_t *data = NULL; 
	heap = (heap_t*)malloc(sizeof(heap_t));
	if(NULL == heap)
	{
		return NULL;
	}
	memset(heap, 0x0, sizeof(heap_t)); 
	data = (uint32_t*)malloc(sizeof(uint32_t)*size);
	memset(data, 0x0, sizeof(uint32_t)*size); 
	if(NULL == data)
	{
		free(heap);
		heap = NULL;
		return NULL;        
	}
	heap->cursize = 0;
	heap->maxsize = size;       
	heap->element = data;
	return heap;      
}
/*释放堆所占用的资源*/
void heap_free(heap_t *heap)
{
	free(heap->element);
	heap->element = NULL;
	free(heap);
	heap = NULL;
}
/*判断堆是否已满*/
bool heap_full(heap_t *heap)
{
	if(heap->cursize >= heap->maxsize)
		return true;
	else
		return false;    
}
/*判断堆是否为空*/
bool heap_empty(heap_t *heap)
{
	if(heap->cursize == 0)
		return true;
	else
		return false;    
}
/*按顺序输出堆元素*/
void heap_out(heap_t *heap)
{
        int i = 0;
        for(i=0; i < heap->cursize; i++)
        {
                printf("%d\t",heap->element[i]);
        }
        printf("\n");
}

小根堆

/*向堆中插入一个元素*/
void minheap_insert(heap_t *heap, uint32_t elem)
{
	int i = 0;
	if(heap_full(heap))
	{
		printf("heap is full, insert failed.\n");
		return;
	}
	for(i = heap->cursize; i > 0 && heap->element[i/2] > elem; i /=2)
	{
		heap->element[i] = heap->element[i/2];  
	}
	heap->element[i] = elem;
	heap->cursize++;
	return;
}

/*删除根节点*/
void minheap_delete(heap_t *heap)
{
	int i = 0, child = 0;
	uint32_t minelem = 0, lastelem = 0;
	if(heap_empty(heap))
	{
		printf("heap is empty, delete failed.\n");
		return;
	}
	minelem = heap->element[0];
	lastelem = heap->element[heap->cursize-1];
	for(i = 0; i*2 < heap->cursize; i = child)
	{
		child = i*2 + 1;
		if(child + 1 < heap->cursize && heap->element[child+1] < heap->element[child])
			child++;
		if(child < heap->cursize && lastelem > heap->element[child])
			heap->element[i] = heap->element[child];
		else
			break;
	}
	heap->element[i] = lastelem;
	heap->cursize--;
	return;
}

大根堆

/*向堆中插入一个元素*/
void maxheap_insert(heap_t *heap, uint32_t elem)
{
	int i = 0;
	if(heap_full(heap))
	{
		printf("heap is full, insert failed.\n");
		return;
	}
	for(i = heap->cursize; i > 0 && heap->element[i/2] < elem; i /=2)
	{
		heap->element[i] = heap->element[i/2];
	}
	heap->element[i] = elem;
	heap->cursize++;
	return;
}

/*删除根节点*/
void maxheap_delete(heap_t *heap)
{
	int i = 0, child = 0;
	uint32_t minelem = 0, lastelem = 0;
	if(heap_empty(heap))
	{
		printf("heap is empty, delete failed.\n");
		return;
	}
	minelem = heap->element[0];
	lastelem = heap->element[heap->cursize-1];
	for(i = 0; i*2 < heap->cursize; i = child)
	{
		child = i*2 + 1;
		if(child + 1 < heap->cursize  && heap->element[child+1] > heap->element[child])
			child++;
		if(child < heap->cursize && lastelem < heap->element[child])
			heap->element[i] = heap->element[child];
		else
			break;
	}
	heap->element[i] = lastelem;
	heap->cursize--;
	return;
}

测试程序

void minheaptest()
{
	int i = 0;
	heap_t *heap = heap_malloc(20);
	if(heap == NULL)
		return;
	for(i = 0; i < 10; i++)
	{
		minheap_insert(heap, i);
	}
	minheap_insert(heap, 5);
	minheap_delete(heap);
	heap_out(heap);
	heap_free(heap);
}

void maxheaptest()
{
	int i = 0;
	heap_t *heap = heap_malloc(20);
	if(heap == NULL)
		return;
	for(i = 0; i < 10; i++)
	{
		maxheap_insert(heap, i);
	}
	maxheap_insert(heap, 5);
	maxheap_delete(heap);
	heap_out(heap);
	heap_free(heap);
}

int main(int argc, char *argv[])
{

	printf("\nmin heap test:\n");
	minheaptest();
	printf("\nmax heap test:\n");
	maxheaptest();
	return 0;
}

测试结果