堆排序
首先我们有一个数组arr，他的里面有一些元素，如果要我们找到这里面的最小值，我们是不是要去扫描一遍这个数组？如果这个时候他要求我们去找一个次小值，或者删除这个数且加一个数进来问你最小值，那我们是不是得又扫描一遍，这样重复n次就扫描了n次也就是0[n]的效率，n一大就gg，那这个时候怎么办呢？堆出现了。
堆是一个完全二叉树，所有顶点的左子树和右子树都比他本身要小，这就叫最大堆（大根堆）因为这样一来他的根就是就是最大值，所有顶点的左子树和右子树都比他本身要大这就是最小堆（小根堆）。这样我们求这个数组的最小值就可以访问堆顶元素即可。
堆的应用，求第n个数里第k小，第k大的数，排序；
一个问题
为什么堆排序（升序）时用最大堆优于最小堆，那是不是降序的时候最小堆优于最大堆,他妈的害我设计了一个自动化的实验，程序都写出来了才发现这个问题根本就是我记错了导致的！仔细思考就能发现，无论是最小堆还是最大堆，pop操作都是需要swap(1,n)然后向下调整，向下调整的时间都是logN有什么区别啊靠。
其实这里说的是在找第k小的时候，建立一个大小为k的最大堆比较方便（遍历完了堆顶就是他了），找第k大的时候建立一个大小为k的最小堆，遍历完堆顶就是他了。mmp我居然搞了大概两个小时。
堆的手写实现（可能有点搓）
手写之前注意四个点
- 如图
-
this.papa.index=[this.index/2];(向下取整)
-
如何维护一个堆的特征，从两个方面考虑(i=this.index)
- 元素在数组尾部，需要向上调整（ if(arr[i]<arr[papa(i)])swap(i,pre(i)) ;）
- 元素在数组头部，需要向下调整(类比上面的就行了)
-
如何创建一个堆？可以从零开始一个一个的加入但是这样太慢了，我们可以直接把无序的数组直接给他，然后从arr.length/2这个地方，也就是第二排（arr.length/2一定对应第二排最后一个元素）每个元素向下调整即可
建立堆的时间复杂度是
class heap{
public:
int a[Max + 1];
int length;
int pre(int nowI);//返回papa坐标
int l(int nowI);//返回左子树坐标
int r(int nowI);//返回右子树坐标
bool creat();
bool print();
void shiftDownMin(int nowI);//向下调整
void shiftUpMin(int nowI);//向上调整
int deletBestMin();//pop最小的元素
void addMin(int val);
};
void heap::addMin(int val) {//增加一个元素，在尾部加然后向上调整
a[++length] = val;
shiftUpMin(length);
}
int heap::deletBestMin() {
int t = a[1];//把根保留一下以便返回
a[1] = a[length--];//把最后一个元素拿到前面来这里也没法拿第别的，不然结构变了
shiftDownMin(1);//向下调整
return t;
}
int heap :: pre(int nowI) {
return nowI / 2;//直接向下取整没有问题
}
int heap::l(int nowI) {
if(nowI * 2 <= length)
return nowI*2;
return nowI;
}
int heap::r(int nowI) {
if (nowI * 2 + 1 <= length)
return nowI*2+1;
return nowI;
}
void heap::shiftDownMin(int nowI) {
if (a[nowI] > a[l(nowI)] || a[nowI] > a[r(nowI)]) {
if (a[l(nowI)] < a[r(nowI)]) {
swap(&a[nowI], &a[l(nowI)]);
shiftDownMin(l(nowI));
}else {
swap(&a[nowI], &a[r(nowI)]);
shiftDownMin(r(nowI));
}
}
}
void heap::shiftUpMin(int nowI) {
if (a[nowI] < a[pre(nowI)]) {
swap(&a[nowI], &a[pre(nowI)]);
shiftUpMin(pre(nowI));
}
}
bool heap::creat() {
cin >> length;
for (int i = 1; i <= length; i++) {
scanf("%d", &a[i]);
}
for (int i = length/2; i >= 1; i--){
shiftDownMin(i);
}
return 1;
}
堆的stl实现
#include <queue>//需要这个头文件
using namespace std;//以及这个命名空间
typedef struct {
int i, v;
}node;
inline bool operator < (const node &n1, const node &n2) {//用结构体的话需要重载运算符
return n1.v < n2.v;
}
priority_queue<node, vector<node>, greater<node>> hep;//最小堆的声明
priority_queue<int, vector<int>, less<int>> maxHeap; //这是最大堆
//priority_queue<Type, Container, Functional>
hep.size():返回堆内元素个数。
hep.empty():如果堆为空，返回真，否则返回假。
hep.top():返回堆顶元素。
hep.pop():删除堆顶元素，自动整理。
hep.push(int x):插入一个元素，自动整理。
这是一种方式，另外一种用algorithm库
void put(int x){//用于插入元素
hep[++len]=x;//len表示堆中元素个数
push_heap(hep+1,hep+1+len);//就像排序一样
}
int get(){//用于得到堆顶元素
pop_heap(hep+1,hep+1+len);
//这个函数会将堆顶放到堆尾，所以后面是hep[len--];
return hep[len--];
}
//创建一个堆
vector<int> v2{6, 1, 2, 5, 3, 4};
make_heap(v2.begin(), v2.end(), greater<int>());//greater是最小堆，这里也可以是自己的比较函数
v1.push_back(200);//push_back仅用于在尾部增加元素
push_heap(v1.begin(), v1.end());//仅用于把最后一个元素向上调整，push_heap(1,n)前需要确保[1,n-1]已经是个堆
//printcontainer(v1, "after push_heap: "); // after push_heap: 200 5 6 1 3 2 4
pop_heap();//它的作用是：交换*first和*(last-1)， 然后把[first, last-1)建成一个max heap. 也就是说把堆顶的最大元素交换到区间尾，然后把除了尾部的元素的剩余区间重新调整成堆。
pop_back();//上面的只是交换，并没有取走，也就是end迭代器没有减减;
sort_heap( RandomIt first, RandomIt last, Compare comp );//即经典的堆排序算法，通过每次弹出堆顶直到堆为空，依次被弹出的元素就组成了有序的序列了。STL中的priority_queue即使用heap的这个特性来实现。
相关阅读
序言 对于堆排序的学习，实际上就是对于 堆 这一种数据结构的学习，把堆学会了，堆排序自然也就学会了。1、为什么使用堆这种数据结构
一、堆排序算法原理和动态图解 将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将
选择排序的基本思想是：每一趟（例如第i趟）在后面的 n-i+1 个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第 n-1
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 算法分析 在学习堆排序之前我们要先