堆的介绍

首先，堆的前提：完全二叉树，添加时就是从最下面最左。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想：堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

**步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

上面来自orz
感谢
我对堆排序的理解：

如果让你构建一个堆的话，首先你可以用数组给他存下来，当然这是又可以让数组下标为0，或者1 为堆顶，我习惯用1，
**你选择一个结点是i，则他父亲结点是i/2; 他的左叶子结点是 2i; 右叶子结点是2i+1；**如果是从零开始：他的父亲节点是（i-1）/2；左叶子结点 2i+1; 右叶子结点：2i+2;

如果是大顶堆的话就是把大的放数组前面，也就是把大的放在父亲节点，找出最大的之后，把最大的与堆尾元素换一下，也就把最大的存放到数组最后一位了，然后进行剩下的比较，同样操作拿出最大的放在堆尾…这样就得到一个递增的数列。
如果是武学构建堆的话，就从最后一个叶子结点的父亲结点（c）处开始，之后再找结点（c-1）；一直找到堆顶。

有一个小栗子可以看一下帮助理解吧；

问题 C: Leopard学霸
来自UPC。
题目描述
马上假期就要到了，THU的神犇Leopard假期里都不忘学霸，现在有好多门功课，每门功课都耗费他1单位时间来学习。他的假期从0时刻开始，有1000000000个单位时间（囧rz）。在任意时刻，他都可以任意一门功课（编号1~n）来学习。因为他在每个单位时间只能学习一门功课，而每门功课又都有一个截止日期，所以他很难完成所有n门功课。对于第i门功课，有一个截止时间Di，若他能学完这门功课，他能够获得知识Pi。在给定的功课和截止时间下，Leopard能够获得的知识最多为多少呢？
输入
第一行，一个整数n，表示功课的数目接下来n行，每行两个整数，Di和Pi
输出
输出一行一个整数，表示最多学得的知识数
样例输入 Copy
3
2 10
1 5
1 7
样例输出 Copy
17
提示
样例说明：第一个单位时间学习第3个功课（1，7），然后在第二个单位时间学习第1个功课(2，10）
【数据范围】
10%数据满足：n<=25
60%数据满足：n<10000
100%数据满足：1<=n<=100000,Di、Pi<=1000000000 最后的答案可能超过32位整型。
思路就是；堆排列，就是先是需要瞒住时间要求，在满足时间条件的前提下，比较大小，小的减下去，把大的加上。也就是一个不断在更新的过程。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
map<string,ll> mp;
priority_queue<ll> qq;
ll f[maxn],a[maxn],b[maxn],n,m,p,flag,temp,sum;
char str[10][10];

struct node{
	int a,b;
}q[maxn];
bool cmp(node a,node b){
	return a.a<b.a;
}

void up(int now){//保证堆首一定是最小的 就是可以用后面的替换 
	while(now > 1 && a[now] < a[now/2]){//把最小的换到堆首
		swap(a[now],a[now/2]);
		up( now / 2);
	}
}

void down(int now){
	while(a[now*2]<a[now]||a[now*2+1]<a[now]){//比较左右子树 
		int w=now*2;//先比较左右子树谁更小，因为根节点要最小的 
		if(a[now*2+1]<a[now*2])w++;
		swap(a[w],a[now]);
		down(w);//继续下面子树的比较 
	}
}

int main (){
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld%lld",&q[i].a,&q[i].b);
	}
	sort( q+1, q+1+n, cmp);
	
	memset( a, inf, sizeof(a));
	
	for(int i=1;i<=n;i++)
	{
		if(m+1<=q[i].a){//可行 
			sum+=q[i].b;
			m++;
			a[++p]=q[i].b;
			up(p);//就是把这个数存放里面之后需要排序
		}else if(a[1]<q[i].b){//满足 堆顶元素比这个元素小就是用这个元素替换掉堆顶元素 
			sum=sum-a[1]+q[i].b;
			a[1]=q[i].b;
			down(1);//既然换掉了所以排序被打乱，就需要在排 ，这个就得从上往下排了，因为这个堆顶变了。
		}
	}
	cout<<sum<<endl;
	
	return 0;
}

补充

最近学会用优先队列来写堆了，上面的，堆排序其实就是把他从大到小，或者从小到大，

priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小

这样直可以表示大根堆和小根堆，至于能不能用这样的法做上面的那个栗子有待于验证，嘻嘻

堆排序

堆

堆的介绍

上面来自orz 感谢 我对堆排序的理解：

补充

上面来自orz
感谢
我对堆排序的理解：