優先隊列的實作--二叉堆

// 二叉堆 -- 用于優先隊列的實作
// 完全二叉樹的 I 結點的 兩個 child 是 I*2 and I*2+1 . --二叉樹的性質
// 完全二叉樹的 I 結點的 father 是 I/2 .  --二叉樹的性質
// 隊列結構 -> head -> queue -> bottom -> 
// head in, bottom out
// 
/*
test data 一共10個數字 輸入輸出的時候需要更改 
12
8
3
5
6
7
15
1 
10
9
Output:1 3 5 6 7 8 9 10 15
*/
#include <cstdio>
#include <iostream>
using namespace std;

const int MAXQ = 10000;
int head; // 隻需要隊列入口的指向   

int prority_queue[MAXQ];


void swap(int& a,int& b){
	a^=b^=a^=b;
}


bool is_empty(){
	return head - 1;
}

void InQueue(int a){
	int node = head;
	int father = node /2 ; // /2
	prority_queue[head++] = a;
	while(prority_queue[node] < prority_queue[father]){
		swap(prority_queue[node], prority_queue[father]);
		node = father;
		father = node /2 ; // /2
	}
	 // ensure right child bigger than left child, impossible!!

}

int DeQueue(){
	int val = prority_queue[1]; // the bottom of queue 
	int node = 1;
	int temp_head = prority_queue[--head]; // let the head element out queue
	while(node*2 < head){
		int temp_node = node; // save father node
		node = node << 1; // *2
		if (node+1 == head || prority_queue[node] < prority_queue[node+1]) // choose the smaller rise
			swap(prority_queue[node],prority_queue[temp_node]);
		else{ // 可以再優化
			swap(prority_queue[node+1],prority_queue[temp_node]);
			node = node + 1;
		}
	}
	prority_queue[node] = temp_head; // make the original element into the blank site
	int father = node /2 ; // /2  adjust the element to a appropriate site
	while(prority_queue[node] < prority_queue[father]){
		swap(prority_queue[node], prority_queue[father]);
		node = father;
		father = node /2 ; // /2
	}
	prority_queue[head] = 0;

	return val;
}

void init(){
	head = 1; // queue start with '1'
	memset(prority_queue,0,sizeof(prority_queue));
	int n,a;
	n = 10;
	for (int i = 0 ; i < n ;i++){
		cin >> a;
		InQueue(a);
	}

}

int main()
{
//	freopen("in.txt","r",stdin);
	init();

	for (int i = 0 ; i < 10 ;i++){
		cout << DeQueue() << " ";
	}

	return 0;
}
           

HDU1102（最小生成樹prime算法） 這個題目寫了一下午+一晚上,一開始還沒有了解過stl裡面的優先隊列是怎麼實作的，于是就去看了看關于優先隊列的實作。才知道優先隊列是可以用二叉堆實作的（附上人家的連接配接： 二叉堆），然後就手寫了一個int型的優先隊列，于是我就想着看來離AC不遠了，然後當回過頭來看題目的時候發現按我的思路資料居然用一個數組放不下，看來還得結構體，于是把int型的改成了結構體的，然後又發現按我的思路這個圖還應帶有方向，然後又改成有向圖。就這樣改來改去，還帶點小粗心。直到剛剛才給ac了。