minheap.h

来自「该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现」· C头文件 代码 · 共 79 行

#ifndef MINHEAP_H
#define MINHEAP_H
#include<iostream.h>
template<class T>
class minHeap
{
private:
	T vector[30];
	int count;
public:
	minHeap()	{count=0;}
	void insert(T el)
	{
		if(count==30)
			cout<<"minHeap is full!"<<endl;
		else if(count==0)
		{
			vector[0]=el;
			count++;
		}
		else
		{
			int i=count;
			while(i!=0 && vector[(i+1)/2-1]>el)
			{
				vector[i]=vector[(i+1)/2-1];
				vector[(i+1)/2-1]=el;
				i=(i+1)/2-1;
			}
			if(i==count)
				vector[count]=el;
			count++;
		}
	}
	T delHead()
	{
		if(count==0)
		{
			cout<<"minHeap is empty!"<<endl;
			return NULL;
		}
		else if(count==1)
		{
			count--;
			return vector[0];
		}
		else
		{
			T tmp,a=vector[0];
			vector[0]=vector[count-1];
			count--;
			for(int i=1;2*i<=count;)
				if(vector[i-1]>vector[2*i-1] && (2*i==count || vector[2*i-1]<=vector[2*i]))
				{
					tmp=vector[i-1];
					vector[i-1]=vector[2*i-1];
					vector[2*i-1]=tmp;
					i=2*i;
				}
				else if(vector[i-1]>vector[2*i] && vector[2*i-1]>=vector[2*i])
				{
					tmp=vector[i-1];
					vector[i-1]=vector[2*i];
					vector[2*i]=tmp;
					i=2*i+1;
				}
				else	break;
			return a;
		}
	}
	void print()
	{
		for(int i=1;i<=count;i++)
			cout<<vector[i-1]<<" ";
		cout<<endl;
	}
};

#endif