寫給自己看的二叉堆(1)：基本操作

也就是一棵完全二叉樹。堆頂最大則為大根堆，堆頂最小則為小根堆，這裡實作的是小根堆。

1.定義

用一個數組來存儲資料。

typedef int eletype;

typedef struct heapstruct
{
	int capacity;
	int size;
	eletype *arr; //used for saving data
}Heap;
           

2.建立一個二叉堆

給二叉堆配置設定空間，給存儲資料用的數組配置設定空間。

Heap *CreateHeap(int max)
{
	Heap *H;
	H = malloc(sizeof(Heap));
	if (H == NULL) {
		printf("Out of space\n");
		return NULL;
	}

	H->arr = malloc(sizeof(eletype) * (max + 1));
	if (H->arr == NULL) {
		printf("Out of space\n");
		return NULL;
	}

	H->capacity = max;
	H->size = 0;
	H->arr[0] = 0;

	return H;
}
           

3.插入

上濾找到合适的插入位置。

void Insert(Heap *H,  eletype data)
{
	if (H->size == H->capacity) {
		printf("Heap is full\n");
		return;
	}
	int i;
	for (i = ++H->size; data < H->arr[i / 2]; i /= 2 )
		H->arr[i] = H->arr[i / 2]; //precolate up
	H->arr[i] = data;
}
           

4.删除最小元素（堆頂）

為了保證删除後仍是一個完整的二叉堆，要将原堆頂以下的資料進行适當的上濾。

eletype DeleteMin(Heap *H)
{
	if (H->size == 0) {
		printf("Heap is empty\n");
		return 0;
	}
	eletype min = H->arr[1];
	eletype last = H->arr[H->size--]; //--!
	int i, child;
	for(i = 1; i * 2 <= H->size; i = child) {
		//Find smaller child
		child = i * 2;
		if (child != H->size && H->arr[child + 1] < H->arr[child])
			child++;
		//precolate one leve
		if (last > H->arr[child])
			H->arr[i] = H->arr[child];
		else
			break;
	}
	H->arr[i] = last;
	return min;
}