最优合并问题.cpp

最优合并问题 给定K个排好序的序列s1,s2,...,sk,用2 路合并算法将这k个序列合并成一个序列。 假设所采用的2路合并算法合并2个长度分另为m 和n的序列需要m+n-1次比较。试设计一个

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

//定义一个最小堆的模板类
template <class Type>
class MinHeap
{
	private:
		int currentSize,maxSize;
		Type *heap;
	public:
		MinHeap(int minHeapSize=10);
		~MinHeap()
		{
			delete[] heap;
		}
		int Size()
		{
			return currentSize;
		}
		Type Min()
		{
			if(currentSize==0) //当堆为空时,返回整数的最小值
				return INT_MIN;
			return heap[1];
		}
		MinHeap<Type>& insert(const Type& x);
		MinHeap<Type>& deleteMin(Type& x);
		void intialize(Type a[],int size,int arraySize);
		void Deactivate() //防止调用堆的构造函数时将数组a删除
		{
			heap=0;
		}
};

template<class Type>
MinHeap<Type>::MinHeap(int minHeapSize)
{
	
	maxSize=minHeapSize;
	heap=new Type[maxSize+1];
	currentSize=0;
}

template<class Type>
void MinHeap<Type>::intialize(Type a[],int size,int arraySize)  //初始化堆
{
	delete[] heap;
	heap=a;
	currentSize=size;
	maxSize=arraySize;

	for(int i=currentSize/2;i>=1;i--) //从具有儿子的最后一个节点开始调整
	{
		Type temp=heap[i];
		int child=2*i;
		while(child<=currentSize)
		{
			if(child<currentSize&&heap[child]>heap[child+1])
				child++;
			if(temp<=heap[child])
				break;
			heap[child/2]=heap[child];   //儿子节点上移
			child*=2;           //儿子节点下标下移
		}
		heap[child/2]=temp;
	}
}

template<class Type>
MinHeap<Type>& MinHeap<Type>::insert(const Type& x)
{
	int i=++currentSize; //插在最后一个叶子节点的后面
	while(i!=1&&x<heap[i/2])
	{
		heap[i]=heap[i/2]; 
		i/=2;        //父节点下标上移
	}
	heap[i]=x;       //保存插入节点
	return *this;
}

template<class Type>
MinHeap<Type>& MinHeap<Type>::deleteMin(Type& x) //删除最小堆中的跟节点,即所有数中最小值
{
	x=heap[1];
	Type temp=heap[currentSize--];
	int i=1,child=2;
	while(child<=currentSize)
	{
		if(child<currentSize&&heap[child]>heap[child+1])
			child++;    //找到两个儿子中最小的那个儿子
		if(temp<=heap[child])  //是否可以直接插入
			break;
		heap[i]=heap[child];
		i=child;       //父节点下移
		child*=2;
	}
	heap[i]=temp;
	return *this;
}

int MaxNum(int [],int);
int MinNum(int [],int);

void main()
{
	fstream inFile,outFile;
	int n;
	inFile.open("input.txt",ios::in);
	if(!inFile)
	{
		cout<<"Can not open input.txt!"<<endl;
		abort();
	}
	inFile>>n;
	int *numArray=new int[n+1];
	for(int i=1;i<=n;i++)
		inFile>>numArray[i];
	int minNum=MinNum(numArray,n);  //求最小值 
	int maxNum=MaxNum(numArray,n);  //求最大值
	cout<<maxNum<<endl;
	cout<<minNum<<endl;
	outFile.open("output.txt",ios::out);
	if(!outFile)
	{
		cout<<"output.txt can not open!"<<endl;
		abort();
	}
	outFile<<maxNum<<" "<<minNum;
	cout<<"results have been saved into output.txt!"<<endl;
	delete[] numArray;
}

int MaxNum(int a[],int n)  //求最多比较次数
{
	int maxNum=0,temp=a[n];
	for(int i=n-1;i>=1;i--)
	{
		temp+=a[i];
		maxNum+=temp-1;
	}
	return maxNum;
}

int MinNum(int a[],int n) //求最少比较次数
{
	MinHeap<int> array(1);
	array.intialize(a,n,n);
	int *tempArray=new int[n+1];
	for(int i=1;i<=n;i++)
	{
		tempArray[i]=a[i]; //把数组a的内容保存起来
	}
	int x,y;
	int temp,minNum=0;
	for(i=0;i<n-1;i++)
	{
		array.deleteMin(x);
		array.deleteMin(y);
		temp=x+y;
		array.insert(temp);
		minNum+=temp-1;
	}
	array.Deactivate();
	array.intialize(tempArray,n,n);
	for(i=1;i<=n;i++) //堆排序
	{
		array.deleteMin(x);
		a[i]=x;  //a数组把数据按从小到大的顺序排列
	}
	array.Deactivate();
	return minNum;
}