[编程珠玑读书笔记]优先队列

以前学数据结构的时候，学到后面一些抽象一点的数据结构，老师也不让我们写代码，也没有强调这些东西的重要性。再加上那时候不懂事，都没有具体去实现过堆，总认为这是很复杂的东西，其实学会以后真是简单的不得了，而且是又简单，又好用。

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
template<class T>
class priqueue{
	private:
		int n,maxsize;
		T *x;
		void swap( int i, int j)
		{
			T t = x[i]; x[i] = x[j]; x[j] = t;
		}

	public:
		priqueue( int m)
		{
			maxsize = m;
			x = new T[maxsize + 1];
			n = 0;
		}

		void insert( T t)
		{
			int i, p;
			x[++n] = t;
			//插入新元素到小根堆，将自己的值和父亲的值做比较
			for( i = n; i > 1 && x[ p = i / 2] > x[i]; i= p)
				swap( p, i);
		}
		T extractmin()
		{
			int i,c;
			//提取最小的元素，也就是第一个元素，再将最后一个元素放在第一个的位置，然后向下移动，保持小根堆
			T t = x[1];
			x[1] = x[ n-- ];
			for( i = 1; ( c = 2 * i ) <= n; i = c)
			{
				if( c + 1 <= n && x[ c + 1 ] < x[c])
					c++;
				if( x[i] <= x[c] )
					break;
				swap( c, i);
			}
			return t;
		}
};

int main()
{
	srand(5);
	int i;
	priqueue<int> queue( 20 );
	for( i = 0; i < 20; i++)
		queue.insert( rand() % 500 );
	for( i = 0; i < 20; i++)
		cout << queue.extractmin() << "\t";
	cout << endl;
	return 0;
}

编程珠玑书本实例：