学步园

    最近学了一下C++ 的泛型，想实践一下，于是写了一个泛型的优先级队列，并且用优先级队列实现了一个堆排序，很简洁。欢迎大家提意见。

    如何实现一个优先级队列？要解决的两个关键问题便是入队和出队之后仍能保持小顶堆的性质。入队的元素不断的和父节点做比较，直到某个父节点比自己小或相等。出队后，让堆顶元素不断和两个孩子中的较小者比较，直到小于或等于较小的孩子。

    现在在考虑如何添加一个比较器，使这个优先级队列可以建成一个大顶堆。

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 100;

//用小顶堆做数据结构存储数据
template<typename T>
class priorityQueue
{
private:
	T data[Max];
	int length; //堆的大小，下标从1到length

	void swap( int i, int j)
	{
		T temp;
		temp = data[i];
		data[i] = data[j];
		data[j] = temp;;
	}

	void siftUp(int last) //新入队的元素跟父节点逐层比较
	{
		for(int i=last; i>1 && data[i] < data[i/2]; i /= 2)
		{
			swap(i, i/2);
		}
	}

	void siftDown(int first) //出队后，堆顶元素和子元素逐层比较
	{
		for(int i=first * 2; i <=length; i *= 2)
		{
			//i指向孩子中较小的那个孩子
			if(i+1 <= length && data[i+1] < data[i])	i++; 
	
			//让较小的孩子同父节点比较
			if(data[i/2] <= data[i])
				break;
			else
				swap(i/2, i);
		}
	}

public:

	priorityQueue()
	{
		length = 0;
	}

	T front()
	{
		return data[1];
	}

	void push(T key)
	{
		data[++length] = key;
		siftUp(length);
	}

	void pop()
	{
		swap(1, length);
		length --;
		siftDown(1);
	}

	int size()
	{
		return length;
	}

	bool empty()
	{
		return length == 0;
	}
};


int main()
{
	priorityQueue<float> q;
	float num;

	//利用优先级队列实现一个堆排序
	while(cin >> num && num != 0)
	{
		q.push(num);
	}
	while(!q.empty())
	{
		cout << q.front() << ' ' ;
		q.pop();
	}
	system("pause");
	return 1;
}

      我自己测了几组测试数据，都通过了。下面给出1组浮点型的。

      96.1 11.2 27.3 38.6 9.3 83.2 0