优先队列的实现

STL中有priority_queue可以实现优先队列。

下面的代码是小堆哦，是从小到大的顺序。

#include <stdio.h>

#define MAX_N 2001

int heap[MAX_N];
int size;

void push(int x) {
	int i = size++;
	int p;

	while (i > 0) {
		p = (i - 1) / 2;
		if (heap[p] < x) {
			break;
		}

		heap[i] = heap[p];
		i = p;
	}

	heap[i] = x;
}

int pop() {
	int res = heap[0];
	int x = heap[--size];
	int i = 0;
	int a, b;

	while (i*2 + 1 < size) {
		a = i*2 + 1;
		b = i*2 + 2;
		if (b < size && heap[b] < heap[a]) {
			a = b;
		}

		if (heap[a] >= x) {
			break ;
		}

		heap[i] = heap[a];
		i = a;
	}

	heap[i] = x;

	return res;
}

int main() {
	int a[] = {8, 4, 3, 5, 6, 7, 9};
	int i;

	for (i = 0; i < 7; i++) {
		push(a[i]);
	}

	for (i = 0; i < 7; i++) {
		printf("%d  ", pop());
	}
	printf("\n");

	return 0;
}