heap.cpp

停车场问题：一个关于堆栈操作的程序

#include <iostream>
#include <cstdlib>
#include <vector>
#include <time.h>

using namespace std;

const maxheapsize=100;

template<class t>
class heap{
public:
	heap(t arr[],int n);
	int liatsize();
	int listempty();
	int listfull();
	t dele();
	void insert(t &iterm);
	void heapsort(t a[],int n);
private:
	t *hlist;
    int heapsize;
	void filterup(int);
	void filterdown(int);
};


template<class t>        //接受从main()中的数组a和heapsize=n，并且完成堆排序
heap<t>::heap(t arr[],int n){
	int currentpos;
	if(n<=0) cout<<"Bad lisr size!";
	heapsize=n;
    hlist=arr;	
	currentpos=(heapsize-2)/2;
	while(currentpos>=0)//完成堆排序
        {
		filterdown(currentpos);
		currentpos--;
	}
}
template<class t>
void heap<t>::insert(t &iterm){
	if(heapsize==maxheapsize) cout<<"heap is full!";
	else{
		hlist[heapsize]=iterm;
		filterup(heapsize);
		heapsize++;
	}
}
template<class t>
void heap<t>::filterup(int i){
	int currentpos,parentpos;
	t target;
	currentpos=i;
	parentpos=(i-1)/2;
	target=hlist[i];
	while(currentpos!=0){
		if(hlist[parentpos] <= target) break;
		else{
			hlist[currentpos] = hlist[parentpos];
			currentpos=parentpos;
			parentpos=(currentpos-1)/2;
		}
	}
	hlist[currentpos]=target;
}
template<class t>
t heap<t>::dele(){
	t tempitem;
	if(heapsize==0) cout<<"heap is empty!";
	tempitem=hlist[0];
	hlist[0]=hlist[heapsize-1];
	heapsize--;
	filterdown(0);
	return tempitem;
}
template<class t>
void heap<t>::filterdown(int i){
	int currentpos,childpos;
	t target;
	currentpos=i;
	target=hlist[i];
	childpos=2*i+1;
	while(childpos < heapsize){
		if( (childpos+1 < heapsize) &&
			(hlist[childpos+1] <= hlist[childpos]) )
			childpos+=1;
		if(target <= hlist[childpos]) break;
		else{
			hlist[currentpos]=hlist[childpos];
			currentpos=childpos;
			childpos=2*currentpos+1;
		}
	}
	hlist[currentpos]=target;
}
template<class t>
int heap<t>::listempty(){
	int iden=0;
	if(heapsize==0) iden=1;
	return iden;
}

template<class t>
heapsort(t a[],int n){
	heap<t> h(a,n); 
	t elt;
	for(int i=n-1;i>=1;i--){
		elt=h.dele();
		a[i]=elt;  //数组a中存储的是任务的时间。
	}
}
template<class t>
void lpt(t* a,int n,int m)//接受main()中任务组a，任务个数n，机器个数m
{
	machinenode b[maxheapsize];//生成个数为m的机器组
	if(n<=m){
		cout<<"schedul one job per machine."<<endl;
		return;
	}
	heap<machinenode> heapb(b, m);//生成个数为m的机器堆
	heapsort(a,n);
	machinenode temp;
	int time=0;
    for(int i=0;i<m;i++)//初始化机器堆
	{ b[i].id=i; b[i].avail=0; }
	cout<<endl<<"begine schedule:"<<endl;
	for(int j=n-1;j>=0;j--){ 
	   temp=heapb.dele();     
	   cout<<"schedule job "<<(a[n-j-1].id+1)
		   <<" consume "<<a[n-j-1].time<<" hours "
		   <<" on machine "<<(temp.id+1)
		   <<" from "<<temp.avail<<" to ";
	   temp.avail+=a[n-j-1].time; 
	   cout<<temp.avail<<endl;
	   if(time<=temp.avail) time=temp.avail;
	   heapb.insert(temp);
	}
	cout<<endl<<"the "<<n<<" jobs will be finished in "<<time<<" hours!"<<endl;
}
class jobnode{
public:
	bool operator<= (const jobnode& node);
	jobnode& operator= (jobnode& node);
    jobnode():id(0),time(0) {}
    jobnode(int id_, int time_):id(id_),time(time_) {}
    int id;
    int time;
};

bool jobnode::operator<= (const jobnode& node)
{
	return (time <= node.time);
}
jobnode& jobnode::operator= (jobnode& node)
{
	time = node.time;
    id=node.id;
	return *this;
}

class machinenode{
public:
	bool operator<= (const machinenode& node);
	machinenode& operator= (machinenode& node);
    int id;
    int avail;
};

bool machinenode::operator<= (const machinenode& node)
{
	return (avail <= node.avail);
}
machinenode& machinenode::operator= (machinenode& node)
{
	avail = node.avail;
    id=node.id;
	return *this;
}


main(){
	jobnode a[maxheapsize],temp1;
	int n=0;//任务的个数
	int m=0;//机器的个数
	while(1){
	cout<<endl<<"Please enter number of job(less then 100):";
	cin >> n;
	cout<<"Please enter number of machine(less then 100):";
	cin >> m;
	if((n>0)&&(n<=100)&&(m>0)&&(m<=100)) break;
	}
	srand(time(0));
	for(int i=0;i<n;i++)//初始化任务节点
    {
		a[i].id = i;
		a[i].time = (1+rand()%n); 
	}
	heap<jobnode> h(a, n);
	cout<<endl<<"job array is ready:"<<endl;
	for(int j=0;j<n;j++){
		cout<<"No."<<(a[j].id+1)<<"job:"<<a[j].time<<" hours"<<";   "; 
		if(((j+1)%4)==0) cout<<endl;
	}

	lpt(a,n,m);
    return 0;
}