什么堆？

• 堆就是用数组实现的完全二叉树结构（除叶节点以外，所有节点都是非空，且叶节点从左到右排列）。
• 完全二叉树中如果每颗子树的的最大值都在顶部就是大根堆。
• 完全二叉树中如果每颗子树的的最小值都在顶部就是小根堆。
• 堆结构就是heapInsert与heapfy操作。
• 堆结构的增加和减少。
• 优先级队列就是堆结构。

堆的heapInsert与heapfy操作

数组：1 9 4 8 2 6

索引：0 1 2 3 4 5

对应的完全二叉树结构：

索引 i：i的左孩子对应的索引2*i+1

i的右孩子对应的索引2*i+2

i的父节点对应的索引(i-1)/2

• heapInsert操作

某个位置处在index位置上往上继续移动，自下而上，构建大根堆/小根堆---------heapinsert操作

#include
#include
using namespace std;
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector&arr, int index)
{
	int parent = (index - 1) / 2;
	while (arr[index] > arr[parent])
	{
		swap(arr[index], arr[parent]);
		index = parent;
		parent = (index - 1) / 2;
	}
}

int main()
{
	vectorarr = { 1,9,4,8,2,6 };
  
	for (int i = 0; i < arr.size(); i++)
	{
		heapinsert(arr, i);
	}
  
	for (auto e : arr)
	{
		cout << e << " ";
	}
	return 0;
}

运行结果：

• heapfy操作

某个数在index位置，能否往下移动，自上而下，构建大根堆/小根堆---------heapfy操作

#include
#include
using namespace std;

//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector&arr, int index, int heapsize)
{
	//左孩子下标
	int left = 2 * index + 1;

	//两个孩子中谁大，就把下标给largest
	while (left < heapsize)  //左孩子存在
	{
		int largest;
		if ((left + 1 < heapsize) && arr[left + 1] > arr[left])
		{
			largest = left + 1;
		}
		else
		{
			largest = left;
		}

		if (arr[largest] > arr[index])
		{
			largest = largest;
		}
		else
		{
			largest = index;

		}

		if (largest == index)
		{
			break;
		}
		swap(arr[largest], arr[index]);

		index = largest;
		left = index * 2 + 1;

	}
}

int main()
{
	vectorarr = { 1,9,4,8,2,6 };
	for (int i = arr.size()-1; i >= 0; i--)
	{
		heapify(arr, i, arr.size());
	}
  
	int len = arr.size();
	for (auto e : arr)
	{
		cout << e << " ";
	}
	return 0;
}

运行结果：

堆排序

• 基本思想

用数组来模拟构建大根堆，完成数组的升序或降序。

• 堆排序算法代码

（1）升序----构建大根堆

#include
#include
using namespace std;

//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector&arr, int index)
{
	while (arr[index] > arr[(index - 1) / 2])
	{
		swap(arr[index], arr[(index - 1) / 2]);
	}
}

//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector&arr, int index, int heapsize)
{
	//左孩子下标
	int left = 2 * index + 1;

	//两个孩子中谁大，就把下表给largest
	while (left < heapsize)  //左孩子存在
	{
		int largest;
		if ((left + 1 < heapsize) && arr[left + 1] > arr[left])
		{
			largest = left + 1;
		}
		else
		{
			largest = left;
		}

		if (arr[largest] > arr[index])
		{
			largest = largest;
		}
		else
		{
			largest = index;

		}

		if (largest == index)
		{
			break;
		}
		swap(arr[largest], arr[index]);

		index = largest;
		left = index * 2 + 1;
	}
}

//堆排序----升序
void heap_sort(vector&arr,int len)
{
	if (len < 2) return;
  //heapinsert构建大根堆
	//for (int i = 0; i < len; i++)
	//{
	//	heapinsert(arr, i);
	//}
  
  //heapfy构建大根堆
	for(int i = len - 1; i >=0; i--)
	{
		heapify(arr, i, len);
	}
	int heapsize = len;
	swap(arr[0], arr[--heapsize]);

	while (heapsize > 0)
	{
		heapify(arr, 0, heapsize);
		swap(arr[0], arr[--heapsize]);
	}
}

int main()
{
	vectorarr = { 1,9,4,8,2,6 };
	int len = arr.size();
	heap_sort(arr, len);
	for (auto e : arr)
	{
		cout << e << " ";
	}
	return 0;
}

运行结果：

（2）降序---构建小根堆

#include
using namespace std;
#include

//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector& arr, int index)
{
	int parent = (index - 1) / 2;
	while (arr[index] < arr[parent])
	{
		swap(arr[index], arr[parent]);
		index = parent;
		parent = (index - 1) / 2;
	}
}


//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector& arr, int index, int heapsize)
{
	//左孩子下标
	int left = 2 * index + 1;

	//两个孩子中谁大，就把小标给small
	while (left < heapsize)  //左孩子存在
	{
		int small;
		if ((left + 1 < heapsize) && arr[left + 1] < arr[left])
		{
			small = left + 1;
		}
		else
		{
			small = left;
		}

		if (arr[small] < arr[index])
		{
			small = small;
		}
		else
		{
			small = index;

		}

		if (small == index)
		{
			break;
		}
		swap(arr[small], arr[index]);

		index = small;
		left = index * 2 + 1;

	}
}

//堆排序,降序
void heap_sort(vector& arr, int len)
{
	if (len < 2) return;

	//heapinsert构建小根堆
	for (int i = 0; i < len; i++)
	{
		heapinsert(arr, i);
	}

	//heapfy构建小根堆
	//for (int i = len - 1; i >= 0; i--)
	//{
	//	heapify(arr, i, len);
	//}

	int heapsize = len;
	swap(arr[0], arr[--heapsize]);

	while (heapsize > 0)
	{
		heapify(arr, 0, heapsize);
		swap(arr[0], arr[--heapsize]);
	}
}

int main()
{
	vector arr = { 1,9,4,8,2,6 };
	//for (int i = 0; i < arr.size(); i++)
	//{
	//	heapinsert(arr, i);
	//}

	//for (int i = arr.size() - 1; i >= 0; i--)
	//{
	//	heapify(arr, i, arr.size());
	//}
	heap_sort(arr, arr.size());

	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << " ";
	}

	return 0;
}

运行结果：

算法特性

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定