堆排序

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define INCCAPACITY 100  
 
typedef int ElemType;
struct heap_operation; //前向声明
 
typedef struct Heap    //堆结构
{
	int capacity;  //容量
	int size;      //现有元素数量
	ElemType *data;  //指针，指向数组
        struct heap_operation *heap_op; // 操作函数
}Heap;
 
typedef struct heap_operation  //里面有一堆函数指针，类似于C＋＋的虚表
{
	void (*init_heap)(Heap *heap, ElemType *_data, int capacity, int size);
	void (*build_heap)(Heap *heap);
	ElemType (*get_min)(Heap *heap);
	ElemType (*delete_min)(Heap *heap);
	void (*insert)(Heap *heap, ElemType e);
}heap_operation;
 
int left_child(int index)  //得到一个元素的左孩子下标
{
	return 2*index+1;
}
 
int right_child(int index) //得到一个元素的右孩子下标
{
	return 2*index+2;
}
 
int parent(int index)   //得到一个元素的父结点下标
{
	return (index-1)/2;
}
 
// 将元素下沉，这是堆操作的核心。
void filter_down(Heap *heap, int index)
{
	ElemType ele = heap->data[index];
	int i = index;
	int child=0;
	for(i=index; i*2+1 <= heap->size-1; i=child)
	{
		child = 2*i + 1;
		if(child < heap->size-1 && heap->data[child] > heap->data[child+1])
			child++;
		if(heap->data[child] < ele)
			heap->data[i] = heap->data[child];
		else
			break;
	}
	heap->data[i] = ele;
}
 
//初始化堆
void init_heap(Heap *heap, ElemType *_data, int capacity, int size)
{
	heap->capacity = capacity;
	heap->size = size;
	heap->data = _data;
}
 
 
// 建堆
void build_heap(Heap *heap)
{
	int i = parent(heap->size - 1);
	while(i>=0)
	{
		filter_down(heap, i);
		i --;
	}
}
 
ElemType get_min(Heap *heap)
{
	return heap->data[0];
}
 
void resizeheap(Heap *heap)
{
	ElemType * p;
	p = (ElemType *)malloc((heap->capacity+INCCAPACITY)*sizeof(ElemType));
	if(p==NULL)
        {
		printf("ERROR at line %d\n", __LINE__);
		exit(0);
	}
	memcpy(p, heap->data, sizeof(ElemType)*heap->capacity);
	heap->capacity += INCCAPACITY;
	free(heap->data);
	heap->data = p;
}
 
// 插入一个元素
void insert(Heap *heap, ElemType e)
{
	int i = 0;
	if(heap->size == heap->capacity) 
		resizeheap(heap);
	heap->data[heap->size] = e;
	heap->size++;
	i  = heap->size - 1;
	while(parent(i)>=0)
	{
		if(heap->data[parent(i)]>e)
		{
			heap->data[i] = heap->data[parent(i)];
			i = parent(i);
		}
		else
			break;
	}
	heap->data[i] = e;
}
 
ElemType delete_min(Heap *heap)
{
	ElemType i = heap->data[0];
        heap->data[0] = heap->data[ heap->size-1 ];
	heap->size --;
 
	filter_down(heap, 0);
	return i;
}
 
void print_array(ElemType array[], int n)
{
	int i = 0;
	while(i<n)
	{
		printf("%d ", array[i++]);
	}
	printf("\n");
}
 
void print_heap(Heap *heap)
{
	print_array(heap->data, heap->size);
}
 
int main()
{
	ElemType e;
        ElemType a[] = {30, 6, 7, 4, 5, 1, 6, 1};
	Heap aheap;
 
	heap_operation heap_op;
	heap_op.init_heap = init_heap; 
        heap_op.build_heap = build_heap;
	heap_op.get_min = get_min;
	heap_op.delete_min = delete_min;
        heap_op.insert = insert;
 
	aheap.heap_op = &heap_op;
 
	aheap.heap_op->init_heap(&aheap, a, sizeof(a)/sizeof(a[0]), sizeof(a)/sizeof(a[0]));
	aheap.heap_op->build_heap(&aheap);
 
	print_heap(&aheap);
 
	printf("min of the array %d\n", aheap.heap_op->get_min(&aheap));
        e = aheap.heap_op->delete_min(&aheap);	
	print_heap(&aheap);
 
	aheap.heap_op->insert(&aheap, e);
	print_heap(&aheap);
 
 
	return 0;
}