minpq.h

金元平版数据结构 实验答案 有关飞机场内容的实验

#ifndef MINPQ_H
#define MINPQ_H

const int DefaultSize = 64;

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
struct element
{
	T data;
	int key;
	element(){};
	element(T d, int k);
	const element& operator=(const element& right);
	void evaluate(T d, int k);
};

template <class T>
element<T>::element(T d, int k)
{
	data = d;
	key = k;
}

template <class T>
const element<T>& element<T>::operator=(const element<T>& right)
{
	data = right.data;
	key = right.key;
	return *this;
}

template <class T>
void element<T>::evaluate(T d, int k)
{
	data = d;
	key = k;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
class minPQ
{
public:
	virtual bool Insert(const element<T>&) = 0;
	virtual bool Delete(element<T>&) = 0;
};

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
template <class T>
class minHeap : public minPQ<T>
{
public:
	minHeap(int sz = DefaultSize);
	bool Insert(const element<T>& item);
	bool Delete(element<T>& x);
	bool isFull();
	bool isEmpty();
	int curSize();
	void reSize( int s );

private:
	element<T>* heap;
	int currentSize;
	int maxSize;
};

template <class T>
minHeap<T>::minHeap(int sz = DefaultSize)
{
	maxSize = sz;
	currentSize = 0;
	heap = new element<T>[maxSize+1];
}

template <class T>
bool minHeap<T>::Insert(const element<T>& x)
{
	if (currentSize>=maxSize)
		return false;

	currentSize++;
	for ( int i=currentSize; (i>1)&&(x.key<heap[i/2].key); i/=2 )
		heap[i] = heap[i/2];
	heap[i] = x;

	return true;
}

template <class T>
bool minHeap<T>::Delete(element<T>& x)
{
	if (currentSize<=0)
		return false;

	x = heap[1];
	element<T> k = heap[currentSize];
	currentSize--;

	int i=1;
	for (int j=2; j<=currentSize; j*=2)
	{
		if( (j<currentSize)&&(heap[j].key>heap[j+1].key) )
			j++;
		if (k.key <= heap[j].key)
			break;
		heap[i] = heap[j];
		i = j;
	}
	heap[i] = k;

	return true;
}

template <class T>
bool minHeap<T>::isFull()
{
	return (currentSize>=maxSize);
}


template <class T>
bool minHeap<T>::isEmpty()
{
	return (currentSize==0);
}

template <class T>
int minHeap<T>::curSize()
{
	return currentSize;
}

template <class T>
void minHeap<T>::reSize( int s )
{
	maxSize = s;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

#endif