minheap.h

实现八数码算法

#include "eightdigit.h"
#include <iostream>
using namespace std;
class MinHeap{   
public:   
	MinHeap(EightDight* a[],int n);   
	MinHeap(int ms);   
	~MinHeap();   
	bool Insert( EightDight* &x);//插入一个元素,如果空返回false，否则返回true   
	bool RemoveMin(EightDight* &x);//删除最小的元素，如果空返回false，否则返回true   
	void MakeEmpty();//使堆为空   
	bool IsEmpty();   
	bool IsFull();   
	void FilterDown(const int start,const int endOfHeap);//自顶向下构造堆   
	void FilterUp(const int start);//自底向上构造堆   
private:   
	EightDight **heap;   
	int maxSize;   
	const int defaultSize;   
	int currentSize;   
};   

MinHeap::MinHeap(int ms):defaultSize(100){   
	maxSize = ms > defaultSize ? ms : defaultSize;   
	heap = new EightDight*[maxSize];   
	currentSize = 0;   
}   
MinHeap::MinHeap(EightDight* a[],int n):defaultSize(100){   
	maxSize = n > defaultSize ? n : defaultSize;   
	heap = new EightDight*[maxSize];   
	currentSize = n;   
	heap = a;   
	int curPos = (currentSize - 2) / 2;   
	while(curPos >= 0){   
		FilterDown(curPos,currentSize - 1);   
		curPos--;   
	}   
}   

MinHeap::~MinHeap(){   
	delete []heap;   
}   

void MinHeap::FilterDown(const int start,const int endOfHeap){   
	int i = start,j = i * 2 + 1;   
	EightDight* temp = heap[i];   
	while(j <= endOfHeap){   
		if(j < endOfHeap && heap[j]->evalue > heap[j+1]->evalue) j++;   
		if(temp->evalue < heap[j]->evalue) break;   
		else{   
			heap[i] = heap[j];   
			i = j;   
			j = 2 * i + 1;   
		}   
	}   
	heap[i] = temp;   
}    
void MinHeap::FilterUp(const int start){   
	int i = start, j = ( i - 1 ) / 2;   
	EightDight* temp = heap[i];   
	while(i > 0){   
		if(temp->evalue >= heap[j]->evalue) break;   
		else{   
			heap[i] = heap[j];   
			i = j;   
			j = (i - 1) / 2;   
		}   
	}   
	heap[i] = temp;   
}   
bool MinHeap::RemoveMin(EightDight* &x){   
	if(IsEmpty()){   
		cerr<<"Heap empty!"<<endl;   
		return false;   
	}   
	x = heap[0];   
	heap[0] = heap[currentSize - 1];   
	currentSize--;   
	FilterDown(0,currentSize-1);   
	return true;   
}    
bool MinHeap::Insert( EightDight*& x){   
	if(IsFull()) {   
		cerr<<"Heap Full!"<<endl;   
		return false;   
	}   
	heap[currentSize] = x;   
	FilterUp(currentSize);   
	currentSize++;   
	return true;   
}     
bool MinHeap::IsEmpty(){   
	return currentSize == 0;   
}   


bool MinHeap::IsFull(){   
	return currentSize == maxSize;   
}   


void MinHeap::MakeEmpty(){   
	currentSize = 0;  
}