博客

二叉堆（优先队列）具有结构性和堆序性

结构性为：二叉堆是一棵完全被填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。二叉堆可以用数组表示，对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在位置2i+1上，父亲则在i/2上（小于i/2的最小整数）。

堆序性为：使操作被快速执行的性质称为堆序性。在一个堆中，对于每个节点x，x的父节点中的关键字小于等于x中的关键字，除根节点外（根节点没有父节点）。

优先队列的声明：

struct heapStruct;
typedef struct heapStruct* priorityQueue;


struct heapStruct
{
	int capacity;
	int size;
	int *elements;
};


priorityQueue initialize(int maxElements);
int isFull(priorityQueue h);
void insert(int x, priorityQueue h);
int isEmpty(priorityQueue h);
int deleteMin(priorityQueue h);

初始化：

priorityQueue initialize(int maxElements)
{
	priorityQueue h;
	h = (struct heapStruct*)malloc(sizeof(struct heapStruct));
	if (h == NULL)
		cout << "Out of space!" << endl;
	h->elements = (int *)malloc(sizeof(int)*(maxElements + 1));
	if (h->elements == NULL)
		cout << "Out of space!" << endl;
	h->capacity = maxElements;
	h->size = 0;
	h->elements[0] = INT_MIN;
	return h;
}

插入（上滤（percolate up））：

int isFull(priorityQueue h)
{
	if (h->size == h->capacity)
		return 1;
	else
		return 0;
}


void insert(int x, priorityQueue h)
{
	int i;
	if (isFull(h))
	{
		cout << "Queue is full!" << endl;
		return;
	}
	for (i = ++h->size; h->elements[i / 2] > x; i = i / 2)
		h->elements[i] = h->elements[i / 2];
	h->elements[i] = x;
}

删除（下滤（percolate down））：

int isEmpty(priorityQueue h)
{
	if (h->size == 0)
		return 1;
	else
		return 0;
}


int deleteMin(priorityQueue h)
{
	int i, child;
	int minElement, lastElement;
	if (isEmpty(h))
	{
		cout << "Queue is empty!" << endl;
		return h->elements[0];
	}
	minElement = h->elements[1];
	lastElement = h->elements[h->size--];
	for (i = 1; i * 2 < h->size; i = child)
	{
		child = i * 2;
		if (child != h->size&&h->elements[child + 1] < h->elements[child])
			child++;
		if (lastElement>h->elements[child])
			h->elements[i] = h->elements[child];
		else
			break;
	}
	h->elements[i] = lastElement;
	return minElement;
}