queue.h

一个模拟机场控制飞机起飞降落及查询功能的程序。

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

//template <class Type>
//struct Element
//{
//	Type key;                            //关键字
//};

template <class Type>
class MinHeap                            //最小堆
{
public:
	MinHeap(int sz = 7);
	bool IsFull();
	void Insert(Type& item);
	bool IsEmpty();
	Type* Delete();                       //删除最小元素
	Type* Root();                         //返回根结点
    int Size();
private:
	Type *heap;
	int n;                                //最小堆的当前元素个数
	int MaxSize;                          //能容纳的最大元素个数
};

template <class Type>
MinHeap<Type>::MinHeap(int sz)
{
	MaxSize = sz;
	n = 0;
	heap = new Type [MaxSize + 1];     //heap[0]不用
}

template <class Type>
bool MinHeap<Type>::IsEmpty()
{
	if(!n)
		return true;
	else
		return false;
}

template <class Type>
bool MinHeap<Type>::IsFull()
{
	if(n == MaxSize)
		return true;
	else
		return false;
}

template <class Type>
void MinHeap<Type>::Insert(Type& x)
{
	if(n == MaxSize)
	{
//		HeapFull();
		return;
	}
	n++;
	for(int i = n; i > 1;)                    //i==1表示已达到根结点
	{
		if(x.fuel >= heap[i/2].fuel)
			break;
		heap[i] = heap[i/2];
		i /= 2;
	}
	heap[i] = x;
}

template <class Type>
Type* MinHeap<Type>::Delete()
{
	Type x;
	if(!n)
	{
//		HeapEmpty();
		return 0;
	}
	x = heap[1];
	Type k = heap[n];
	n--;
	for(int i = 1, j = 2; j <= n;)            //j是i的子女
	{
		if(j < n)
			if(heap[j].fuel > heap[j+1].fuel)   //j指向较小子女
				j++;
			if(k.fuel <= heap[j].fuel)
				break;
			heap[i] = heap[j];
			i = j;
			j *= 2;
	}
	heap[i] = k;
	return &x;
}

template <class Type>
Type* MinHeap<Type>::Root()
{
	if(!n)
	{
//		HeapEmpty();
		return 0;
	}
	return &heap[1];
}

template <class Type>
int MinHeap<Type>::Size() {
	return n;
}