cminheap.h

是编译器我花了好几个礼拜才编好的确实难的这是个不错的编译器

#ifndef CMINHEAPH
#define CMINHEAPH

#include "stdafx.h"

// Min-heap class
/**************************************************************
Comp类中只有一个公有静态成员函数 为BiggerThan 用于判断大小
**************************************************************/


class Compare
{
public:
	static bool BiggerThan(CBinTreNode<int> * a,CBinTreNode<int> * b){
		return a->m_MData > b->m_MData;
	}
	
};



template <class Elem, class Comp>		
class CMinHeap {

private:
	Elem* m_pEHeap;          // 所用数组的指针
	int m_nSize;            // 数组范围
	int m_nNum;               // 当前小顶堆内的元素个数

public:
	CMinHeap(Elem* h, int num, int max)     // 构造函数
		{ m_pEHeap = h;  m_nNum = num;  m_nSize = max;  BuildHeap(); }
	int GetHeapSize() const       // 返回当前元素个数
		{ return m_nNum; }
	bool IsLeaf(int nPos) const // 返回是否为叶子
		{ return (nPos >= m_nNum/2) && (nPos < m_nNum); }
	int GetLeftChd(int nPos) const
		{ return 2*nPos + 1; }    // 得到左孩子的数组下标
	int GetRigChd(int nPos) const
		{ return 2*nPos + 2; }    // 得到右孩子的数组下标
	int GetParent(int nPos) const  // 得到双亲的地址
		{ return (nPos-1)/2; }



	void BuildHeap()           // Heapify contents of Heap
	{ for (int i=m_nNum/2-1; i>=0; i--) Siftdown(i); }


	void Siftdown(int nPos) {	// 筛选调整该位置的元素
		int nAdjust = nPos;
		int nRigChd = 0;
		Elem eTem = m_pEHeap[nPos];
		int nTemPos = nPos;
		while (!IsLeaf(nPos)) {     // 调整 直到调到叶子位置
			nAdjust = GetLeftChd(nPos);  nRigChd = GetRigChd(nPos);
			if ((nRigChd < m_nNum) && Comp::BiggerThan(m_pEHeap[nAdjust], m_pEHeap[nRigChd]))
				nAdjust = nRigChd;        // 找到左右孩子中较小的一个
			if (Comp::BiggerThan(m_pEHeap[nAdjust] , eTem)) {
				if(nTemPos != nPos) m_pEHeap[nPos] = eTem;//如果有移动原nPos位置的数据则赋值
				return;
			}
			else	m_pEHeap[nPos] = m_pEHeap[nAdjust];		//如果比孩子小则调整元素位置
			nPos = nAdjust;         // 调整新的位置
		}
		m_pEHeap[nAdjust] = eTem;	//调整结束 将原来的元素放在相应位置或者叶子节点
	}

	void SiftUp(int nPos){

		int nCurPos = nPos;
		Elem item = m_pEHeap[nPos];			// 从堆底插入元素（可省略）
		while (nCurPos!=0){				// 调整直到是现在所指元素小于他的双亲
			if(Comp::BiggerThan(item ,m_pEHeap[GetParent(nCurPos)]) ) break;
			m_pEHeap[nCurPos] = m_pEHeap[GetParent(nCurPos)];
			nCurPos = GetParent(nCurPos);
		}
		m_pEHeap[nCurPos] = item;
		
	}


	bool Insert(const Elem& item) {	// 在小顶堆中插入元素
		if (m_nNum >= m_nSize) return false; // 堆已满 则无法插入
		int nCurPos = m_nNum;
		m_pEHeap[nCurPos] = item;
		m_nNum++;
		SiftUp(nCurPos);
		return true;
	}

	bool DelTop(Elem& item) {		//删除堆顶元素（最小值） 返回其元素值
		item = m_pEHeap[0];             //返回删除的值
		if (m_nNum == 0) return false; // 堆为空
		m_pEHeap[0] = m_pEHeap[m_nNum -1];
		m_nNum --;
		if (m_nNum != 0) Siftdown(0);  // 调整新的根节点
		m_pEHeap[m_nNum] = item;
		return true;
	}
	
	void PrintArr() const{
		cout<<endl;
		for(int i=0;i<m_nNum;i++){
			cout<<m_pEHeap[i]<<"  ";
		}
		cout<<endl;
	}

	bool Remove(int nPos, Elem& item) {

		cout<<"in Remove   "<<nPos<<endl;
		PrintArr();
		if ((nPos < 0) || (nPos >= m_nNum)) return false; //位置错误
		item = m_pEHeap[nPos];
		m_pEHeap[nPos] = m_pEHeap[m_nNum - 1];
		m_nNum --;
		PrintArr();
		SiftUp(nPos);
		PrintArr();
		Siftdown(nPos);      // 向下调整
		m_pEHeap[m_nNum] = item;
		PrintArr();
		return true;
	}

	void Clear(){
		m_nNum = 0;
	}



};

#endif