030300833offmin.cpp

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

#include<fstream.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
class MinHeap{
public:
	MinHeap(int MinHeapSize = 10);
	~MinHeap() { delete [] heap;}
	int Size()const {return Last;}
	int Min() { 
		if (Last == 0) exit(1);
		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)
{
	if (Last == MaxSize) exit(1);
	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)exit(1) ;
	x = heap[1];
	int y = heap[Last--];
	int i = 1,ci = 2;
	while (ci <= Last)
	{
		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;
}
main()
{
	fstream infile,outfile;
	infile.open("input.txt",ios::in);
	if(!infile)
	{
		cout<<"input.txt can't open";
		exit(1);
	}
	outfile.open("output.txt",ios::out);
	if(!outfile)
	{
		cout<<"output.txt can't open";
		exit(1);
	}
	int n,m,i,x,min;
	infile>>n>>m;
    MinHeap H(n);
	for(i=0;i<n+m;i++)
	{
		infile>>x;
		if(x!=-1)
			H.Insert(x);
		else
		{
			H.DeleteMin(min);
		    outfile<<min<<" ";
		}
	}
	infile.close();
	outfile.close();
	return 1;
}