minheap.h

二叉树

//**************minHeap.h****************//
//******最小堆的类定义和各操作的实现*******//

#ifndef MINTHEAP_H
#define MINTHEAP_H

#include <iostream>

using namespace std;

template<class T>
class MinHeap {
public:
	MinHeap(const int size=20) { 
		maxSize=(size>0)?size:20;
		array=new T[maxSize];
		currentPosition=0;
	}
	~MinHeap() { delete [] array; }
	void insert(                               const T &);  //插入
	void deleteNode(const T &);  //删除
	int search(const T &) const; //查找
	void printAll() const { //打印
		for (int i=0; i<currentPosition; i++)
			cout<<array[i]<<", ";
		cout<<endl;
	}
private:
	T *array;
	int maxSize;
	int currentPosition;
	int parent(const int &) const; //传入参数所在位置的父亲节点位置
	int leftChild(const int &) const; 
	int rightChild(const int &) const;
	void swap(const int &, const int &); //交换两个位置的数据
	void moveUp(int);
	void moveDown(int);
};

template<class T>
int MinHeap<T>::parent(const int &pos) const {
	return int((pos-1)/2);
}

template<class T>
int MinHeap<T>::leftChild(const int &pos) const {
	return pos*2+1;
}

template<class T>
int MinHeap<T>::rightChild(const int &pos) const {
	return pos*2+2;
}

template<class T>
void MinHeap<T>::swap(const int &pos1, const int &pos2) {
	T tmp=array[pos1];
	array[pos1]=array[pos2];
	array[pos2]=tmp;
}

template<class T>
void MinHeap<T>::moveUp(int pos) {
	int par=parent(pos);
	while (par>=0) {
		if (par==0) {
			if (array[pos]<array[par]) {
				swap(pos, par);
				break;
			}
			else break;
		}
		if (array[pos]<array[par]) {
			swap(pos, par);
			pos=par;	
			par=parent(pos);
		}
		else break;
	}
}

template<class T>
void MinHeap<T>::moveDown(int pos) {
	int left=leftChild(pos);
	while (left<currentPosition) {
		if (array[pos]>array[left] && array[left]>array[left+1]) {
			swap(pos, left+1);
			pos=left+1;
			left=leftChild(pos);
		}
		else if (array[pos]>array[left]) {
			swap(pos, left);
			pos=left;
			left=leftChild(pos);
		}
		else break;
	}
}

template<class T>
void MinHeap<T>::insert(const T &data) {
	if (currentPosition==maxSize)
		return;
	array[currentPosition]=data;
	moveUp(currentPosition);
	currentPosition++;
}

template<class T>
void MinHeap<T>::deleteNode(const T &data) {
	int pos=search(data);
	if (pos!=-1) {
		if (pos==currentPosition-1)
			currentPosition--;
		else {
			array[pos]=array[--currentPosition];
			moveDown(pos);
		}
	}
}

template<class T>
int MinHeap<T>::search(const T &data) const {
	for (int i=0; i<currentPosition; i++)
		if (array[i]==data)
			return i;
	return -1;
}

#endif //file end