堆
简单来说堆就是维护一个数据集合，堆的实质是一个二叉树；
堆的性质：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
附上图 嘿嘿~：
今天我们说的小顶堆的堆排列介个问题（我才不会告诉你们我只学了小顶堆~小声bb）~~
储存问题
（这里说一下，因为我们这次是手写堆的教程，跟STL中堆有所不同，4、5操作在STL中是无法完成的，，，还有就是储存问题
STL中堆是使用优先队列进行存储；
手写堆是使用一个一维数组进行存储；（嗯，对的 ，一个一维数组；）
（一般为了方便会把根节点记为1而不是0）
在数组中储存的位置一般就是，第一个为根节点，接下来是根节点的左儿子，，，
（简单来说就是我们第X位置存放根节点的话
它的左儿子为 第2X个位置；
右儿子 第2X+1个位置；
）
主要操作
主要就是两个操作down(x)还有up(x)
所谓 down(x)；
就是从上到下进行处理；
举个栗子~~
若将 1处位置—>4改为10
此时与堆的性质不符，将1处与其左右儿子相比较，找出最小值，交换两处位置，（因为堆顶为最小值）
同理与2处与其左右儿子相比较，，最总结果为：
同理up(x)操作为从下到上搜索
例如
将 5处 9改为—>2；
（与down不同，up只与其父节点比较，，，）
2<8 将3处与5处交换
继续向上搜索 2<4 交换 1处与3处
结束；
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
好，接下来我们康康主要问题
主要问题
主要包括以下5个问题
1.插入一个数X；
插入一个数从末尾插入：
h[++size]=x;
2.求集合中的最小值
最小值就是根节点
h[1]
3.删除最小值
删除事就是用最末尾元素覆盖第一个然后down
h[1]=h[size];
size--;
down(1)；
4.删除任意一个元素(删除第x个）
删除也是用末尾元素覆盖这个元素，，但这个元素需要判断，，这里有个简单的办法就是down 与up都操作一次，，，主意在运行的时候只会选择其一
h[x]=h[size];
size--;
down(x);
up(x);
5.修改任意一个元素(第x个改为xx）
与第四个差不多；
h[x]=xx;
down(x);
up(x);
就介个样子吧
贴个题；
堆排序https://www.acwing.com/problem/content/840/
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+6;
int h[N];
int n,m;
int siz;
void down(int u)
{
int t=u;
if(u*2<=siz&&h[t]>h[u*2])t=u*2;
if(u*2+1<=siz&&h[t]>h[u*2+1])t=u*2+1;
if(u!=t)
{
swap(h[t],h[u]);
down(t);
}
}
int main()
{
// int m;int size;
cin>>n>>m;
siz=n;
for(int i = 1; i <= n; i ++)
cin>>h[i];
for(int i=n/2;i>0;i--)
down(i);
while(m--)
{
cout<<h[1]<<' ';
h[1]=h[siz];
siz--;
down(1);
}
return 0;
}
第一次写多多包涵大家都不容易
哦了，拜拜~~