（1小时数据结构）数据结构c++描述（十八）---堆与最大堆（优先队列）

首先来了解一些概念:

最大树（最小树）:    每个节点的值都大于（小于） 或等于其子节点（如果有的话）值的树。

如下图：

虽然这些树都是二叉树，但最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于 2。

最大堆（最小堆）： 最大（最小）的完全二叉树。

      图9-1b 所示的最大树并不是最大堆（max heap），另外两个最大树是最大堆。图 9-2b 所示的最小树不是最小堆（min heap），而另外两个是。
 

代码部分 

/*
数组结构中 最大堆  完全二叉树

对应书中代码：数据结构算法与应用c++描述

程序编写：比卡丘不皮

编写时间：2020年7月20日 11:17:13
*/
#pragma once
#include <iostream>
#include "all_error.h"
using namespace std;

template<class T>
class MaxHeap
{
public:
	MaxHeap(int HeapSize = 10)
	{
		MaxSize = 10;
		heap = new T[MaxSize+1];
		CurrentSize = 0;
	}
	~MaxHeap() { delete[] heap; }
	//获取当前堆的大小
	T Max()
	{
		if(CurrentSize == 0)
			throw OutOfBounds();
		else
			return heap[1];                        //heap中的元素从1开始
	}
	//向堆中插入元素x，并返回操作之后的堆
	MaxHeap<T> &Insert(const T &x);
	//删除堆顶元素，并返回操作后的堆 
	MaxHeap<T> &DeleteMax(T &x);
	//初始化函数，将一个数组构造成最大堆,size为数组中元素个数，ArrayMaxSize为数组最大容量
	MaxHeap<T> &Initialize(T a[], int size, int ArraySize);
	//输出最大堆
	void Output(ostream &out)
	{
		for (int i = 1; i <= CurrentSize; i++)
			out << heap[i] << "  ";
		cout << endl;
	}
private:
	int CurrentSize, MaxSize; //当前的堆大小  堆的最大规模
	T *heap; // 元素数组
};

 插入函数：

template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T & x)
{

	if (CurrentSize == MaxSize)
	{
		throw OutOfBounds();
	}

	//为x需找应插入位置
	// i 从新的叶节点开始，并沿着树上升
	int i = ++CurrentSize;
	while (i!= 1 && x > heap[i/2])
	{
		//不能够把 x 放入 heap[i]
		heap[i] = heap[i / 2];
		i /= 2;
	}
	heap[i] = x;
	return *this;
}

插入函数流程图 ：

        如图所示，a为堆当前的树型结构，由于堆是最大（小）完全的二叉树，下个节点位置如b的位置，加入要加的节点是21，

此时i 值是b图中灰色的节点，i=i/2; 对应的是c图指向的灰色位置，就是父节点，然后判单当前值与父节点的大小，发现比2大，

2移动到下面，同理在判定c图中灰色节点的父节点，发现比20大，20移动下来，然后把21写入刚才的父节点。这就是插入的过

程。

删除最大值：

template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T & x)
{
	if (CurrentSize == 0)
	{
		throw OutOfBounds();
	}

	x = heap[1]; //取当前最大值
   // 重构堆
	T y = heap[CurrentSize--]; //最后一个元素
	int i = 1, ci = 2; // i的孩子
	while (ci <= CurrentSize)
	{
		if (ci < CurrentSize && heap[ci] < heap[ci+1])
		{
			ci++;
		}
		if (y>=heap[ci])
		{
			break;
		}
		heap[i] = heap[ci];
		i = ci;
		ci *= 2;
	}
	heap[i] = y;
	return *this;
}

 删除过程图：

 首先要删除一个元素一定是最后一个节点要去掉，但是删除了是最大值，也就是根节点，先判断 15 与 2的大小，15大于2,15跑

根节点，然后判断之前15的左右节点，14 与 10，发现14>10,14跑到之前15 的位置，最后10跑到14的位置，结果图c就是结果

图，也是最终的结果。

 初始化数组，然后变成最大堆：

Initialize函数：

template<class T>
MaxHeap<T>& MaxHeap<T>::Initialize(T a[], int size, int ArraySize)
{
	// 把最大堆初始化为数组 a .
	delete[] heap;
	CurrentSize = size;
	MaxSize = ArraySize;
	heap = new T[MaxSize+1];

	for (int i = 0; i < CurrentSize; i++)
	{
		heap[i + 1] = a[i];
	}
	// 产生一个最大堆
	for (int i = CurrentSize / 2; i >= 1; i--)
	{
		T y = heap[i]; // 子树的根
    // 寻找放置 y的位置
	int c = 2 * i; // c的父节点是y的目标位置
	while (c <= CurrentSize)
		{
			// heap[c] 应是较大的同胞节点
			if (c < CurrentSize &&
				heap[c] < heap[c + 1]) c++;
			// 能把 y 放入h e a p [ c / 2 ]吗?
			if (y >= heap[c]) break; // 能
									 // 不能
			heap[c / 2] = heap[c]; // 将孩子上移
			c *= 2; // 下移一层
		}
	heap[c / 2] = y;
	}

	return *this;
}

 过程图：

       如图上面的10个数据，a对应最开始的数组数据，找到最后一个节点的父节点，然后，判断与子节点大小，然后判断是否换位置。以此遍历下面的父节点，最后遍历到根节点后，结束，就排列出入d图中的样子了。

测试函数：

//重载输出操作符"<<"
template <class T>
ostream &operator<<(ostream &out, MaxHeap<T> &MH)
{
	MH.Output(out);
	return out;
}

void testMaxHeap()
{
	int a[] = {20, 12, 35, 15, 10, 80, 30, 17, 2, 1};
	MaxHeap<int> MH(10);
	MH.Insert(2).Insert(3).Insert(4).Insert(5);

	cout << MH << endl;
	int value;
	MH.DeleteMax(value);
	cout << "delete Max is " << value << endl;
	cout << "the array is ";
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

	MH.Initialize(a, 10, 20);
	cout << MH << endl;

	MH.Insert(5);
	cout << MH << endl;

}

 这里写了重载的数据，可以自接输出函数值。

测试结果图：