030300741offmin.cpp

这是一个关于离线最小值的源程序

#include<iostream.h>
#include<fstream.h>

int n,m,i,j=0,x,k;

class MinHeap{
public:
	MinHeap(int MinHeapSize);
	~MinHeap(){delete[] heap;}
	int Size() const{return Last;}
	int Min(){if(Last==0)throw ;return heap[1];}
	MinHeap &Insert(const int &x);
	MinHeap &DeleteMin(int &x);
private:
	int Last,MaxSize;
	int *heap;
};

MinHeap::MinHeap(int MinHeapSize)//构建空堆
{
	MaxSize=MinHeapSize;
	 heap=new int[MaxSize+1];
	Last=0;
	
}
MinHeap &MinHeap::Insert(const int&x)//插入一个元素x
{
	if(Last==MaxSize) throw ;
	int i=++Last;
	while(i!=1&&x<heap[i/2])
	{
		heap[i]=heap[i/2];
		i/=2;}
	heap[i]=x;
	return *this;
}
MinHeap &MinHeap::DeleteMin(int &x)//从堆中抽取最小元
{
	if(Last==0) throw ;
	x=heap[1];
	int y=heap[Last--];
	int i=1,ci=2;
	while(ci<=Last)//搜索y的插入位置
	{
		if(ci<Last&&heap[ci]>heap[ci+1]) ci++;
		if(y<=heap[ci]) break;
		heap[i]=heap[ci];
		i=ci;
		ci*=2;}
	heap[i]=y;
	return *this;
}


void main()
{
	ifstream in ("input.txt");
	ofstream out ("output.txt");
	
	in>>n>>m;
	MinHeap M(n);//构造n个集合
	for (i=0;i<n+m;i++)
	{
		in>>k;
		if(k!=-1)//输入的k不为-1
			M.Insert(k);
		else{
			//输入k为-1
			M.DeleteMin(x);
			out<<x<<" ";
		}
			
	}
	
}