C++实现最大堆

实现代码：

#pragma once

template
class CMyHeap {	//最大堆
	T		*pBuff;	//动态数组
	size_t	len;	//动态数组长度
	size_t	maxSize;//容量
public:
	CMyHeap();
	~CMyHeap();
	void clear();							//清空
	void appendNode(T const& data);			//尾部增加
	void deleteNode();						//删除根节点
	void initHeap(T arr[], size_t srcLen);	//初始化所有元素操作
public:
	T getRoot() const { return *pBuff; }	//得到根节点的值

};

//1、一次在堆内加入所有元素
//2、从最后一个有子节点的节点开始，调整位置，满足最大堆的特性
template
void CMyHeap::initHeap(T arr[], size_t srcLen) {
	clear();
	if (srcLen <= 0)return;

	maxSize = len = srcLen;
	pBuff = new T[maxSize];
	for (size_t i = 0; i < len; ++i) {
		pBuff[i] = arr[i];
	}

	//i为最后一个有子节点的节点的下标
	for (int i = (((int)len - 2) >> 1); i >= 0; --i) {
		int index = i;	//表示需要调整的节点下标
		T tempVal = pBuff[index];
		int leftIndex = 0;
		int rightIndex = 0;
		bool isLeft = true;
		while (true) {
			leftIndex = index * 2 + 1;
			rightIndex = index * 2 + 2;
			if (leftIndex > (len - 1)) {	//左子树下标越界
				break;
			}

			isLeft = true;
			if (rightIndex <= (len - 1)) {	//有右子树
				if (pBuff[leftIndex] < pBuff[rightIndex]) {
					isLeft = false;
				}
			}

			if (isLeft) {	//和左子树比
				if (tempVal < pBuff[leftIndex]) {
					pBuff[index] = pBuff[leftIndex];
					index = leftIndex;
				}
				else {
					break;
				}
			}
			else {	//和右子树比
				if (tempVal < pBuff[rightIndex]) {
					pBuff[index] = pBuff[rightIndex];
					index = rightIndex;
				}
				else {
					break;
				}
			}
		}
		pBuff[index] = tempVal;
	}
}

template
void CMyHeap::deleteNode() {	
	//1、只能删除根节点
	//1、把最后一个节点移动到根节点
	//2、调整根节点的次序
	if (len == 0) return; //空堆

	if (len > 1) {	//堆中有两个以上节点
		pBuff[0] = pBuff[len - 1];
	}
	len--;	
	int index = 0;
	T tempVal = pBuff[index];
	int leftIndex = 0;
	int rightIndex = 0;
	bool isLeft = true;
	while (true) {
		leftIndex = index * 2 + 1;
		rightIndex = index * 2 + 2;
		if (leftIndex > (len - 1)) {	//左子树下标越界
			break;
		}

		isLeft = true;
		if (rightIndex <= (len - 1)) {	//有右子树
			if (pBuff[leftIndex] < pBuff[rightIndex]) {
				isLeft = false;
			}
		}

		if (isLeft) {	//和左子树比
			if (tempVal < pBuff[leftIndex]) {
				pBuff[index] = pBuff[leftIndex];
				index = leftIndex;
			}
			else {
				break;
			}
		}
		else {	//和右子树比
			if (tempVal < pBuff[rightIndex]) {
				pBuff[index] = pBuff[rightIndex];
				index = rightIndex;
			}
			else {
				break;
			}
		}
	}
	pBuff[index] = tempVal;
}

template
void CMyHeap::appendNode(T const& data) {
	if (len >= maxSize) {
		maxSize = maxSize + ((maxSize >> 1) > 1 ? (maxSize >> 1) : 1);
		T* temp = new T[maxSize];
		for (size_t i = 0; i < len; ++i) {
			temp[i] = pBuff[i];
		}
		if (pBuff) {
			delete[] pBuff;
		}
		pBuff = temp;
	}
	pBuff[len++] = data;

	//到这里为止，完成了完全二叉树的操作，但是会破坏最大堆的结构
	//要满足最大堆的原理
	T tempVal = pBuff[len - 1];
	int index = len - 1;
	int parentIndex = 0;
	while (index) {	//纵向，循环往根节点比较
		parentIndex = (index - 1) >> 1;
		if (tempVal > pBuff[parentIndex]) {
			pBuff[index] = pBuff[parentIndex];
			
		}
		else {
			break;
		}
		index = parentIndex;
	}
	pBuff[index] = tempVal;

}

template
CMyHeap::CMyHeap()
{
	pBuff = nullptr;
	len = maxSize = 0;
}

template
CMyHeap::~CMyHeap()
{
	clear();
}

template
void CMyHeap::clear() {
	if (pBuff) {
		delete[] pBuff;
		pBuff = nullptr;
	}
	len = maxSize = 0;
}

主函数：

#include "stdafx.h"
#include "MyHeap.h"

int _tmain(int argc, _TCHAR* argv[])
{
	CMyHeap mt;
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	//mt.initHeap(arr, 10);
	for (int i = 0; i < 10; ++i) {
		mt.appendNode(i + 1);
	}
	for (int i = 0; i < 10; ++i) {
		printf("%dn", mt.getRoot());
		mt.deleteNode();
	}
	return 0;
}