北大oj 3481 c＋＋源代码.cpp

北大OJ上的题目

#include<stdio.h>
#define MAXSIZE 1000000

typedef struct{
	long id;
	long prior;
} elem;

typedef struct{
	elem order[MAXSIZE];
	long length;
} Client;

void MAX_HEAPIFY(Client &a, int i)
{
	long largest, l, r;
	elem temp;
	l = 2*i;
	r = 2*i + 1;
	if(l <= a.length && a.order[i].prior < a.order[l].prior) {
		largest = l;
	} else {
		largest = i;
	} 
	if(r <= a.length && a.order[largest].prior < a.order[r].prior) {
		largest = r;
	}
	if(i != largest) {
		temp = a.order[i];
		a.order[i] = a.order[largest];
		a.order[largest] = temp;
		MAX_HEAPIFY(a, largest);
	}
}

void BUILD_MAX_HEAP(Client &a)
{
	int i;
	for(i = a.length/2; i > 0; i --) {
		MAX_HEAPIFY(a, i);
	}
}

void HEAP_EXTRACT_MAX(Client &a)
{
	if(a.length < 1) {
		printf("0\n");
	} else {
		a.order[0] = a.order[1];
		a.order[1] = a.order[a.length];
		a.length --;
		MAX_HEAPIFY(a, 1);
		printf("%ld\n", a.order[0].id);
	}
}

void INCREASE_KEY(Client &a, long i, long key)
{
	elem temp;
	a.order[i].prior = key;
	while(i > 1 && a.order[i].prior > a.order[i/2].prior) {
		temp = a.order[i];
		a.order[i] = a.order[i/2];
		a.order[i/2] = temp;
		i /= 2;
	}
}

void Insertion(Client &a, elem nelem)
{
	a.length ++;
	a.order[a.length] = nelem;
	INCREASE_KEY(a, a.length, a.order[a.length].prior);
}

int main(void)
{
	int command;
	long max, i;
	Client L;
	elem temp;
	L.length = 0;
	scanf("%d", &command);
	while(command != 0) {
		switch(command) {
			case 1:
				scanf("%ld%ld", &temp.id, &temp.prior);
				Insertion(L, temp);
				break;
			case 2:
				HEAP_EXTRACT_MAX(L);
				break;
			case 3:
				for(i = L.length/2 + 2, max = L.length/2 + 1; i <= L.length;  i++) {
					if(L.order[i].prior < L.order[max].prior) {
						max = i;
					}
				}
				INCREASE_KEY(L, max, L.order[1].prior + 1);
				HEAP_EXTRACT_MAX(L);	
				break;
		}
		scanf("%d", &command);
	}
	return 0;
}