大家好，欢迎来到IT知识分享网。

STL中的greater<>()和less<>()

两个函数的头文件为
排序的时候，默认是从小到大；从大到小排序要使第三个参数为greater()。
建堆的时候，默认是最大堆；最小堆要使第三个参数为greater()。
make_heap等heap操作函数在头文件里## 测试用例

// 排序
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std;

void print(int intNums[], int nLength)
{
	//  依次输出数组元素
	for (int i = 0; i < nLength; i++){
		cout << intNums[i] << " ";
	}
	cout << endl;
}

int main()
{
	int intNums[] = {5, 2, 7, 4, 1, 8, 3, 6, 9};
	int nLength = sizeof(intNums) / sizeof(int);
	sort(intNums, intNums+nLength, greater<int>()); // 按从大到小排序
	print(intNums, nLength);
	sort(intNums, intNums+nLength, less<int>()); // 按从小到大排序
	print(intNums, nLength);
}

Heap

定义

堆是一个完全二叉树，可以用一维数组来存储所有结点，堆分大顶堆和小顶堆。
大顶堆（最大堆）：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆（最小堆）：每个结点的值都小于或等于其左右孩子结点的值。

若一维数组从下标为0处开始存储：arr[i]的左孩子为arr[2i+1], arr[i]的右孩子为arr[2i+2]。（i>=0）(对于大顶堆有 arr[i] >= arr[2i+1] 以及 arr[i] >= arr[2i+2] )
若一维数组从下标为1处开始存储，下标为0处可以存储元素总个数：arr[i]的左孩子为arr[2i]，arr[i]的右孩子为arr[2i+1]。（i>0）

总结一下： 堆是满足堆的属性的完全二叉树（结点为最值，不需要整棵树有序），以一维数组的形式存储，目的是以最快的速度找到最值。（二叉搜索树中搜索会很快，但堆中搜索会很慢）

堆排序

以最大堆为例，堆顶元素是最大值，我们将堆顶元素与最后一个元素交换，然后将剩下的元素调整成最大堆；循环以上步骤，最终数组中的元素将按升序排序。

构建堆

给定数组int nums[]={3,7,4,9,5}

依次从下到上，从右到左调整为最大堆。
按以上顺序依次扫描非叶子结点，若该结点值小于其左/右子树的值，则将该结点与左右子树中最大值的结点进行交换。
最后一个非叶子结点为: length/2-1，再找下一个非叶子结点只要减1就好了，直到找到堆顶元素。
这里最后一个非叶子结点为nums[5/2-1]，即nums[1]==7, 其孩子最大值为9，将7和9交换。

下一个非叶子结点为nums[1-1]，即nums[0]==3。其孩子最大值为9，将3与9交换。
下一步，检查调整后的子树是否满足最大堆的性质，由于只将根结点的值与左子树互换，只需检查左子树是否满足最大堆的性质。若不满足，则按以上步骤，从最后一个非叶子结点依次调整。（可以看到这是一个递归的过程）

最大堆构建完毕！

堆排序

将堆顶元素与最后一个元素互换，将剩余元素调整为最大堆。

循环。



排序结束，此时数组中的元素为{3，4，5，7，9}，按升序排序。

C++的STL中堆的实现

// 初始化堆
vector<int> arr = {3, 4, 7, 9, 2, 5, 8, 1, 6};
make_heap(arr.begin(), arr.end(), less<int>()); // 建立最大堆， O(n)
// make_heap(arr.begin(), arr.end(), greater<int>()); // 建立最小堆

// 判断堆
is_heap(arr.begin(), arr.end()); 

// 插入元素
// 在堆中插入元素每次都是将新数据放在数组最后，然后调整到合适位置。
arr.push_back(20); // 先将元素插入vector中
push_heap(arr.begin(), arr.end()); // 调用 push_heap 调整堆，O(logn)
// 在使用push_heap之前要先建堆，因为push_heap只是将指定区间的最后一个元素插入heap中

// 删除元素
// 堆的删除操作只能删除堆顶元素， 实际操作是将最后一个元素赋值给栈顶元素，然后从栈顶自上而下调整堆
pop_heap(arr.begin(), arr.end(), less<T>());  // 弹出heap顶元素，将其放置于区间末尾，O(logn)
arr.pop_back();


// 堆排序后不是一个真正的堆了
// 每次取出堆顶元素，即排序结果，通过反复调用pop_heap来实现O(nlogn)
sort_heap(arr.begin(), arr.end()); // 容器中的元素按从小到大排序

参考资料：
[1] C++ Heap 堆
[2] C++标准库中的堆-heap
[3] heap c++ 操作 大顶堆、小顶堆
[4] 堆排序C++实现(三个函数，建堆、调整成堆、堆排序)