堆排序
堆性质：
- 堆是一个
完全二叉树 - 堆中某个节点的值
总是不大于或不小于其父节点的值 - 堆的每个结点的值都
小于或等于其左右孩子结点，称为小根堆 - 堆的每个结点的值都
大于或等于其左右孩子结点，称为大根堆
下面分别介绍完全二叉树、小根堆、大根堆
完全二叉树：
- 只允许最后一层有空缺而且空缺只能是右边，而不能是左边
- 完全二叉树通常采用数组来存储
小根堆
- 每个结点的值都小于或等于其左右孩子结点
- 根节点是最小值
大根堆
- 每个结点的值都大于或等于其左右孩子结点
- 根节点是最大值
存储方式
- 一般用数组存储比较方便
用上面小根堆举例子：
手写一个堆
思路
- 插入一个数:
heap[ size] = x; size ++；up(size);（在末尾插入，插入之后堆的大小加1，并且通过up函数上升到相应位置） - 求集合当中的最小值：
heap[1]; (对于小根堆来说，根节点就是最小值) - 删除最小值：
heap[1] = heap[size]; size --;down(1);(删除最小值不能直接删除，不然根节点就为空，所以先和最后一个元素交换，在将最后一个元素删除，最后down到相应的位置)，在数组中删除最后一个元素，比删除第一个元素简单。 - 删除任意一个元素：
heap[k] = heap[size]; size --; down(k); up(k);(思路和删除最小值一样) - 修改任意一个元素：
heap[k] = x; down(k); up(k);
题目 ：堆排序
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1 ≤ m ≤ n ≤ 105
1 ≤ 数列中元素 ≤ 109输入样例：
5 3 4 5 1 3 2输出样例：
1 2 3
代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int heap[N]; //size存的是数组元素的个数，heap存储数组元素
int sizes;
void down(int u)
{
int t = u; //down的时候需要找到三个当中最小的那个，所以先假设u是最小的
if (u * 2 <= sizes && heap[u * 2] < heap[t]) t = u * 2; //首先判断左节点有没有，有的话在判断左节点和根的大小
if (u * 2 + 1 <= sizes && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
if (u != t) //此时t是最小的那个值，u != t说明根节点不是最小的
{
swap(heap[t], heap[u]); //u和t不相等就进行交换。
down(t); //继续迭代，一直到堆根为止
}
}
void up (int u)
{
int t = u;
while (u / 2 && heap[u / 2] > heap[u])
{
t = u / 2;
swap(heap[t], heap[u]);
up(t);
}
}
void up2 (int u)
{
while (u / 2 && heap[u / 2] > heap[u])
{
swap(heap[u / 2], heap[u]);
u /= 2;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &heap[i]);
sizes = n;
//for (int i = n / 2; i; i --) down(i); //建立堆,俩个建堆都可以,时间复杂度O(n)
//for (int i = n; i ; i --) down(i); //时间复杂度是O(nlogn)
for (int i = 1; i <= n; i++) up(i); //这三种方法都可以建堆
while (m --)
{
printf("%d ", heap[1]);
heap[1] = heap[sizes];
sizes --;
down(1);
}
return 0;
}题目： 模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k 个插入的数；C k x，修改第 k 个插入的数，将其变为 x；现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为
I x，PM，DM，D k或C k x中的一种。输出格式
对于每个输出指令
PM，输出一个结果，表示当前集合中的最小值。每个结果占一行。
数据范围
1 ≤ N ≤ 105
−109 ≤ x ≤ 109
数据保证合法。输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM输出样例：
-10 6
代码
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
int heap[N]; //size存的是数组元素的个数，heap存储数组元素
int sizes;
int ph[N],hp[N]; //ph存储第k个插入元素的下标是什么，hp存储的是堆里面的某个点，是第几个插入点，这俩个互为反函数
//只有知道第k个点在哪里再能进行插入和删除。
//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(heap[a], heap[b]);
}
void down(int u)
{
int t = u; //down的时候需要找到三个当中最小的那个，所以先假设u是最小的
if (u * 2 <= sizes && heap[u * 2] < heap[t]) t = u * 2; //首先判断左节点有没有，有的话在判断左节点和根的大小
if (u * 2 + 1 <= sizes && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
if (u != t) //此时t是最小的那个值，u != t说明根节点不是最小的
{
heap_swap(u, t); //u和t不相等就进行交换。
down(t); //继续迭代，一直到堆根为止
}
}
void up (int u)
{
int t = u;
while (u / 2 && heap[u / 2] > heap[u])
{
t = u / 2;
heap_swap(u, t);
up(t);
}
}
int main()
{
int n, m = 0; //m表示当前是第几个插入的数
//注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
//对应上文 m即是hp中应该存的值
scanf("%d%d", &n, &m);
while (n --)
{
char op[10];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
sizes ++;
m ++;
ph[m] = sizes, hp[sizes] = m;
heap[sizes] = x;
up(sizes);
}
else if (!strcmp(op, "PM")) printf("%d\n", heap[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, sizes);
sizes --;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k]; //找到第K个数的下标是什么
heap_swap(k, sizes);
sizes --;
down(k), up(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
heap[k] = x;
down(k), up(k);
}
}
return 0;
}
