二叉堆的实现

1.堆的概念

这里只需要注意两点：

a.堆的存储方式：就是顺序存储在数组中，在二叉树中表现为满二叉树

b.堆的用处：用于排序，查找最大最小都非常方便

 

2.堆的实现

heapexception.h

 

#ifndef HEAPEXCEPTION_H
#define HEAPEXCEPTION_H

class ArrayOverFlowException{
	 public:
		 const char* what() const throw()  
	   {  
	      return  "array over flow exception!\n";
	   }  
};

class ParametersErrorException{
	public:
		 const char* what() const throw()  
	   {  
	      return  "input error parameters exception!\n";
	   }  
};

class UnderFlowException{
	public:
		 const char* what() const throw()  
	   {  
	      return  "the size out of array exception(position <= 0)!\n";
	   } 
};
#endif

 

 heap.h

 

//二叉堆,是一颗被完全填满的二叉树，完全二叉树，故而可以使用顺序存储在数组中
#ifndef HEAP_H
#define HEAP_H

template<class T>
class BinaryHeap{
	public:
		BinaryHeap( );
		BinaryHeap( const T* items, const int size);
		~BinaryHeap();
		
		bool isEmpty() const;
		const T& findMin() const;
		
		void insert( const T x);//注意：插入过程中，如果满了，则要resize
		void deleteMin();
		void deleteMin( T& minItem);
		void makeEmpty();
	private:
		int currentSize;//the number of elements in heap
		int capacity;
		void resize(int capacity);
		T* array;//the heap array
		
		void buildHeap();
		void percolateDown(int hole);//将结点下滤，即从顶至叶子的调整过程
};
#endif

 heap.cpp

 

#include <iostream>
#include "heap.h"
#include "heapexception.h"
using namespace std;

template<class T>
BinaryHeap<T>::BinaryHeap(){
	capacity = 100;
	array = new T[capacity];
	currentSize = 0;
}

template<class T>
BinaryHeap<T>::BinaryHeap( const T* items, const int size){
	if(size <= 0) throw ParametersErrorException();
	currentSize = size;
	capacity = size+10;
	array = new T[capacity];
	for(int i=0; i<size; i++){
		//注意：这里是从1开始存储，主要是为了计算的方便，如1的左右孩子就是1*2,1*2+1,从0就不行
		array[i+1] = items[i];
	}
	buildHeap();
}

template<class T>
BinaryHeap<T>::~BinaryHeap(){
	delete[] array;
}
		
template<class T>
bool BinaryHeap<T>::isEmpty() const{
	if(currentSize == 0) return true;
	return false;
}

template<class T>
const T& BinaryHeap<T>::findMin() const{
	if(currentSize == 0) throw UnderFlowException();
	return array[1];
}

template<class T>
void BinaryHeap<T>::insert( const T x){//注意：插入过程中，如果满了，则要resize
	if(currentSize == capacity-1){
		resize(capacity);
	}
	//在最后建立一个空的位置，如果满足条件则上浮
	int hole = ++currentSize;
	for(; hole>1 && x < array[hole/2]; hole/=2){
		array[hole] = array[hole/2];
	}
	array[hole] = x;
	
}

template<class T>
void BinaryHeap<T>::deleteMin(){
	if(currentSize == 0) throw UnderFlowException();
		//将当前最新的交换到最后，在进行一次下滤
	array[1] = array[currentSize--];
	percolateDown(1);
}

template<class T>
void BinaryHeap<T>::deleteMin( T& minItem){
	if(currentSize == 0) throw UnderFlowException();
	minItem = array[1];
	array[1] = array[currentSize--];
	percolateDown(1);
}

template<class T>
void BinaryHeap<T>::makeEmpty(){
	currentSize = 0;
}

template<class T>		
void BinaryHeap<T>::buildHeap(){
	cout<<"build heap\n";
	//建堆的过程就是从低到顶的将结点下滤
	for(int i=currentSize/2; i>0; i--){
		percolateDown(i);
	}
}

//将结点下滤，即从顶至叶子的调整过程(小根堆)
template<class T>
void BinaryHeap<T>::percolateDown(int hole){
	int child;
	T tmp = array[hole];
	for(; hole*2 <= currentSize; hole = child){
		child = hole*2;
		if(child != currentSize && array[child+1] < array[child]){//右子树
			child++;
		}
		//如果当前比hole小，交换
		if(array[child]<tmp){
			array[hole] = array[child];
		}else{
			break;
		}
	}
	//hole是最后交换的位置
	array[hole] = tmp;
}

template<class T>
void BinaryHeap<T>::resize(int capacity){
	T* t = array;
	capacity = currentSize*2 + 1;
	array = new T[capacity];
	for(int i=0; i<currentSize; i++){
		array[i+1] = t[i];
	}
	delete t;
}

 main.cpp

 

#include <iostream>
#include "heapexception.h"
#include "heap.cpp"
using namespace std;

int main(){
	int a[] = {59, 48, 75, 98, 86, 23, 37, 59};
	try{
		BinaryHeap<int> bh(a, 8);
		int min;
		cout<<"------------------------\n";
		cout<<bh.isEmpty()<<endl;
		cout<<"min:"<<bh.findMin()<<endl;
		bh.deleteMin(min);
		cout<<"min:"<<bh.findMin()<<endl;
		
		cout<<"insert"<<endl;
		bh.insert(10);
		cout<<"min:"<<bh.findMin()<<endl;
		bh.makeEmpty();
		bh.findMin();
	}catch(ArrayOverFlowException e){
		cout<<e.what()<<endl;
	}catch(ParametersErrorException e){
		cout<<e.what()<<endl;
	}catch(UnderFlowException e){
		cout<<e.what()<<endl;
	}
	
	return 0;
}