最大堆、最小堆的构造，利用堆实现数组排序的C++代码

一、什么是堆？

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

简单点说堆就是满足特定条件的完全二叉树，这里的“特定条件”分两种：即要么这棵树所有的节点都不大于（小于等于）其根节点（如果有）的值，如下图所示就称为最大堆。

要么这棵树所有的节点都不小于（大于等于）其根节点的值，如下图所示的称为最小堆。

一句话，对于一颗完全二叉树，根节点总最大时叫最大堆，根节点总最小时叫最大堆。

二、如何构造一个堆

以构建最大堆为例，为了方便起见，不妨用一个一维数组来表示一颗完全二叉树，例如：

int heap[] = { 16,4,10,14,7,9,3,2,8,1 };

已知heap是一个完全二叉树，自然能够画出它的等效结构：

显然heap不是最大堆，为了使其满足最大堆结构，我们需要对二叉树的结构进行调整。

为了保证每次调整都向最大堆的目标更进一步，我们应当自下而上对节点调整。具体思路是：对于除了叶子节点外的任一节点A，假设其两个孩子节点分别为B、C，如果A的值不是最大的，则将节点A和最大的那个节点（B或者C）交换。考虑到A节点被下放之后可能会影响已经调整好的子树，再递归一下就好了。我们从右至左，自下而上的重复这个操作，即可构建最大堆。

1. 第一个小目标：实现一颗最小子树的调整。需要注意的细节是倘若已知根节点下标，如何表示其左孩子和右孩子下标。第三个参数heap_size可以暂时理解为数组的长度，接下来会提到。

void MaxHeapIFY(int *heap,int index,int heap_size)
{//寻找当前节点和其左右孩子中的最大值并交换,因为实际是自下而上操作,所以默认当前节点的左右子树都已是最大堆
	int left = 2 * index + 1;
	int right = left + 1;
	int largest = index;
	if (left < heap_size && heap[left]>heap[index]) // not out of index
		largest = left;
	if (right<heap_size && heap[right]>heap[largest])
		largest = right;
	if (largest != index) // 交换最大节点
	{
		int temp = heap[largest];
		heap[largest] = heap[index];
		heap[index] = temp;
		//如果当前堆发生改变，则递归地操作后续堆以适应最大堆结构
		MaxHeapIFY(heap, largest, heap_size);
	}
}

2.对除了叶子结点外的所有节点执行调整操作，这里需要注意的细节是叶子结点在数组中的下标为heap_size/2-1

void BuildMaxHeap(int* heap,int heap_size)
{
	for (int i = (heap_size) / 2 - 1; i >= 0; i--)
	{
		MaxHeapIFY(heap, i,heap_size);
	}
}

然后在主函数中进行如下操作，就将heap成功调整为最大堆结构了~

BuildMaxHeap(heap, sizeof(heap)/sizeof(heap[0]));

调整后的模型如下图：

三、堆排序

倘若我们已经成功将一个数组构造成最大堆（最小堆），那么对数组进行排序这件事就如同探囊取物了——我们每次将数组的第一个元素摘出放到末尾，及时调整堆的结构，就可以实现排序啦！那么我们如何保证已经被摘出的元素不会再参与新的调整呢？这件事是heap_size完成的，每次我们取出最大元素后就让heap_size-1就OK了！

void HeapSort(int* heap, int heap_size)
{
	BuildMaxHeap(heap, heap_size); //heap[0]恒为当前需调整的元素,将其与heap[final]交换并及时调整堆
	for (int final = heap_size-1; final > 0; final--)
	{
		int tmp = heap[0];
		heap[0] = heap[final]; //将堆顶最大元素摆放正确
		heap[final] = tmp;
		MaxHeapIFY(heap, 0, final); //重新调整最大堆,同时heap_size(也就是final的值)在不断变小
	}
}

有了最大堆，自然不难实现最小堆，感兴趣的可以自己实现一下。

除了排序，堆还可以进行插入元素、删除元素、增大元素值等等，就不多介绍了，代码直接放在下面。发blog记录一下学习数据结构&算法的细节，希望共同进步。

#include <iostream>
#include<limits>
using namespace std;
/* heap: An array conclude elements of the HEAP 
   index:current index for operation
   heap_size: max size of the heap
   return: None
   left:2*index + 1 (if exist)
   right:2*index + 2(if exist)
*/ 
void MaxHeapIFY(int *heap,int index,int heap_size)
{//寻找当前节点和其左右孩子中的最大值并交换,因为实际是自下而上操作,所以默认当前节点的左右子树都已是最大堆
	int left = 2 * index + 1;
	int right = left + 1;
	int largest = index;
	if (left < heap_size && heap[left]>heap[index]) // not out of index
		largest = left;
	if (right<heap_size && heap[right]>heap[largest])
		largest = right;
	if (largest != index) // 交换最大节点
	{
		int temp = heap[largest];
		heap[largest] = heap[index];
		heap[index] = temp;
		//如果当前堆发生改变，则递归地操作后续堆以适应最大堆结构
		MaxHeapIFY(heap, largest, heap_size);
	}
}
void MinHeapIFY(int* heap, int index, int heap_size)
{
	int left = 2 * index + 1;
	int right = left + 1;
	int minindex = index;
	if (left < heap_size && heap[left] < heap[index])
		minindex = left;
	if (right < heap_size && heap[right] < heap[minindex])
		minindex = right;
	if (minindex != index)
	{
		int temp = heap[minindex];
		heap[minindex] = heap[index];
		heap[index] = temp;
		MinHeapIFY(heap, minindex, heap_size);
	}
}
// 自下而上对除叶子节点外的节点进行调整
void BuildMaxHeap(int* heap,int heap_size)
{
	for (int i = (heap_size) / 2 - 1; i >= 0; i--)
	{
		MaxHeapIFY(heap, i,heap_size);
	}
}
void BuildMinHeap(int* heap, int heap_size)
{
	for (int i = (heap_size) / 2 - 1; i >= 0; i--)
	{
		MinHeapIFY(heap, i, heap_size);
	}
}
//根据最大堆结构对数组进行堆排序
void HeapSort(int* heap, int heap_size)
{
	BuildMaxHeap(heap, heap_size); //heap[0]恒为当前需调整的元素,将其与heap[final]交换并及时调整堆
	for (int final = heap_size-1; final > 0; final--)
	{
		int tmp = heap[0];
		heap[0] = heap[final]; //将堆顶最大元素摆放正确
		heap[final] = tmp;
		MaxHeapIFY(heap, 0, final); //重新调整最大堆
	}
}
//最大堆应用:优先队列
//HeapMaximum:返回堆中最大元素
//Insert:把元素插入集合S中
//ExtraMax:去掉最大元素并返回
//IncreaseKey(heap,index,k)将元素head[index]关键值增加到k
int Heap_Maximum(int* heap)
{
	return heap[0];
}
//将heap[index]增加为key,关键在于增加值后维持最大堆的结构
int HeapIncreaseKey(int* heap, int index, int key)
{
	if (heap[index] > key)
		return -1;
	heap[index] = key;//key是一个更大的数,所以我们只需关注key和父节点的大小关系
	while (index != 0 && heap[index] > heap[(index + 1) / 2 - 1])
	{//与父节点交换并继续向上寻找，直到找到根节点
		int temp = heap[(index + 1) / 2 - 1];
		heap[(index + 1) / 2 - 1] = heap[index];
		heap[index] = temp;
		index = (index + 1) / 2 - 1;
	}
	return 0;
}
int Heap_Insert(int* heap,int *heap_point, int key)
{
	*heap_point += 1; //指针传递修改堆有效值
	HeapIncreaseKey(heap, *heap_point, key); //将一个INT_MIN修改为key
	return 0;
}
int Heap_ExtraMax(int* heap,int *heap_point)
{
	if (*heap_point == 0)
		return -1;
	int maxvalue = heap[0]; 
	heap[0] = heap[(*heap_point)-1]; //堆尾元素覆盖堆顶
	heap[(*heap_point) - 1] = INT_MIN; //堆尾元素直接覆盖
	(*heap_point)--; //更新堆元素个数
	MaxHeapIFY(heap, 0,*heap_point); //将整个堆重新调整
	return maxvalue;
}
int main()
{
	int heap[] = { 16,4,10,14,7,9,3,2,8,1,INT_MIN,INT_MIN }; // INT_MIN 无穷小,占位以便插入或删除
	int heap_size = 0;
	for(int i:heap)
	{	
		if (i != INT_MIN)
			heap_size += 1;
	}
	cout << "Init Heap:" << endl;
	for (int i : heap)
		cout << i << " ";
	cout <<endl<< "Sorted Heap:" << endl;
	BuildMaxHeap(heap, heap_size);
	//HeapIncreaseKey(heap, 1, 20);
	//Heap_Insert(heap, &heap_size, 20);
	//int maxva = Heap_ExtraMax(heap, &heap_size);
	//cout << "已删除堆顶元素:" << maxva << endl;
	for (int i : heap)
		cout << i << " ";
	cout <<endl<<"堆大小"<< heap_size << endl;
	return 0;		
}