堆排序和优先级队列priority_queue

堆

       堆是完全二叉树，便于用array来储存堆的所有节点；堆存储在下标为0开始计数的数组中，因此在堆中给定下标为i的结点时：

        ① 如果i=0: 结点i是根节点，没有双亲节点；否则结点i的双亲结点为结点(i-1)/2。
        ② 如果2*i+1>n-1: 则结点i无左孩子，否则结点i的左孩子为结点2*i+1。
        ③ 如果2*i+2>n-1: 则结点i无右孩子，否则结点i的右孩子为结点2*i+2。

大根堆与小根堆priority_queue

       根据元素排列方式，heap可分为max-heap和min-heap两种，前者每个节点的键值（key）都大于或等于其子节点键值，后者的每个节点键值（key）都小于或等于其子节点键值。因此，max-heap的最大值在根节点，并总是处于底层array或vector的头部。min-heap的最小值在根节点，总是位于底层array或vector的起头处。

堆排序

       小根堆实现降序排列，大根堆实现升序排列。

       小根堆实现堆排序(降序)基本思想：

       (1) 初始化堆：将数列a[0,...,n-1]构成小根堆；

       (2) 交换数据：将a[0]与a[n-1]交换，使a[n-1]成为a[0,...,n-1]中的最小值；然后将a[0,...,n-2]重新调为小根堆。然后，将a[0]与a[n-2]交换，使a[n-2]成为a[0,...,n-2]中的最小值；然后将a[0,...,n-3]重新调为小根堆。依次类对，直到整个数列a[0,...,n-1]有序(降序)。

       代码如下：

       (1) 递归调整下沉

//  递归调整下沉
void minHeapAdjust(int *arr, int i, int size)           //  i为父节点索引
{
	int left = 2 * i + 1;                           //  left为左孩子节点索引
	int right = 2 * i + 2;                          //  right为右孩子节点索引
	int min = i;                                    //  min为父节点、左节点、右节点中最小值的索引
	if (i < size / 2)                               //  叶子节点不需调整，i>=size/2均是叶子节点
	{
		if (left < size&&arr[min] > arr[left])
			min = left;
		if (right < size&&arr[min] > arr[right])
			min = right;
		if (min != i)                   //  递归返回条件：父节点为最小值则直接返回；
		{                               //  否则交换父节点与最小值节点，然后再继续以min为父节点索引，继续递归调整；
			swap(arr[min], arr[i]);
			minHeapAdjust(arr, min, size);
		}
	}
}

//  建堆
void buildMinHeap(int *arr, int size)
{
	for (int i = size / 2 - 1; i >= 0; i--)//  从第一次非叶子节点开始调整堆(索引为size/2-1的节点为第一个非叶子节点)
	{
		minHeapAdjust(arr, i, size);
	}
}

//  堆排
void minHeapSort(int *arr, int size)
{
	assert(arr != nullptr&&size > 0);  //  检查参数有效性
	buildMinHeap(arr, size);              //  建堆
	for (int i = size - 1; i > 0; i--) //  将arr[0]与arr[n-1]交换，使arr[n-1]成为arr[0,...,n-1]中的最小值；
	{                                  //  然后将arr[0,...,n-2]重新调为小根堆。
		swap(arr[0], arr[i]);      //  再将a[0]与a[n - 2]交换，使a[n - 2]成为a[0, ..., n - 2]中的最小值；
		minHeapAdjust(arr, 0, i);  //  然后将a[0, ..., n - 3]重新调为小根堆。依次类对，直到整个数列有序。
	}
}

        (2) 迭代调整下沉

//  迭代调整下沉
void adjustDown(int *arr, int i, int size)
{
	int child = 2 * i + 1;
	int min = i;
	while (min < size / 2) //  当min>=size/2时，就到达非叶子节点了，非叶子节点有序，结束循环；
	{
		if (child + 1 < size&&arr[child] > arr[child + 1])
			child++;
		if (child<size&&arr[min]>arr[child])
		{
			swap(arr[min], arr[child]);
			min = child;
			child = 2 * min + 1;
		}
		else
			break;  //  父节点本身是min(父，左，右)时，跳出循环；
	}
}

//  建立小根堆
void buildMinHeap(int *arr, int size)
{
	for (int i = size / 2 - 1; i >= 0; i--)
		adjustDown(arr, i, size);
}

//  堆排降序
void minHeapSort(int *arr, int size)
{
	assert(arr != nullptr&&size > 0);
	buildMinHeap(arr, size);                          
	for (int i = size - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);
		adjustDown(arr, 0, i);
	}
}

优先级队列priority_queue

       priority_queue本质是一个堆。

       1. 头文件是#include<queue>

       2. 关于priority_queue中元素的比较

　　模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。

　　Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector。

       比较方式默认用operator<，所以如果把后面2个参数缺省的话，优先队列就是大顶堆，队头元素最大。特别注意pair的比较函数：先按照pair的first元素降序，first元素相等时，再按照second元素降序。

       如果要用到小顶堆，则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。如： priority_queue<int, vector<int>, greater<int> > q;