mini_prio_queue.cpp

最小优先队列的c++模板实现

#include<iostream>
#include<climits>
#include<vector>
using namespace std;

template<class T> class _MinQueue
{
	vector<T> _heap;
	void _Decrease_Key( unsigned&, const T& );
public:
	_MinQueue(){};
	_MinQueue( const vector<T>& );			//The constructor builds a heap with a vector.
	_MinQueue( T* const&, T* const& );		//The constructor builds a heap with an arrqy.
	void _MinHeapfy( const unsigned& );
	T _Extract_Min(void);
	T peek_min(){ return _heap[0]; };
	bool empty(void){ return _heap.empty(); };
	void _Insert( const T& );
	void OUTput(void);///~~~~~~~~~~~~~~~~~~~~~~~FOR DEBUGGING~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	~_MinQueue(void){};						//The destructor do nothing.
};
template<class T> _MinQueue<T>::_MinQueue( const vector<T>& elemt )
{
	_heap = elemt;
	unsigned i = _heap.size() / 2;
	while( i-- )
		_MinHeapfy( i );
}
template<class T> _MinQueue<T>::_MinQueue( T* const& begin, T* const& end )
{
	vector<T> vec( begin, end );
	_heap = vec;
	unsigned i = _heap.size() / 2;
	while( i-- )
		_MinHeapfy( i );
}
template<class T> void _MinQueue<T>::_MinHeapfy( const unsigned& i )
{
	unsigned lft, rht, min;
	unsigned _size = _heap.size();
	lft = 2 * i + 1;
	rht = lft + 1;
	if( lft < _size && _heap[lft] < _heap[i] )
		min = lft;
	else
		min = i;
	if( rht < _size && _heap[rht] < _heap[min] )
		min = rht;
	if( min != i )
	{
		T tmp = _heap[i];
		_heap[i] = _heap[min];
		_heap[min] = tmp;
		_MinHeapfy( min );
	}
};
template<class T> T _MinQueue<T>::_Extract_Min(void)
{
	T min = _heap[0];
	unsigned i = 0;
	_heap[0] = _heap[_heap.size() - 1];
	_heap.pop_back();
	_MinHeapfy(i);
	return min;
}
template<class T> void _MinQueue<T>::_Decrease_Key( unsigned& i, const T& _New_Key )
{
	_heap[i] = _New_Key;
	unsigned _parent = ( i - 1 ) / 2;
	while( i > 0 && _heap[i] < _heap[_parent] )
	{
		T tmp = _heap[i];
		_heap[i] = _heap[_parent];
		_heap[_parent] = tmp;
		i = ( i - 1 ) / 2;
		_parent = ( i - 1 ) / 2;
	}
}
template<class T> void _MinQueue<T>::_Insert( const T& _add )
{
	_heap.push_back( _add );
	if( _heap.size() != 1 )
	{
		unsigned i = _heap.size() - 1;
		_heap[i] = LONG_MAX;
		_Decrease_Key( i, _add );
	}
}
template<class T> void _MinQueue<T>::OUTput(void)
{
	for( unsigned i = 0; i < _heap.size(); i++ )
		cout<<_heap[i]<<endl;
}
int main()
{
	int a[5] = { 5, 3, 6, 2, 7 };
	_MinQueue<int> q( a, a + 5 );
	q.OUTput();
	return 0;
}