数据结构 堆

手写堆，而非stl中的堆

如何手写一个堆？

//将数组建成堆 <O(n)

for (int i = n / 2;i;i--) //从n/2开始down

down(i);

从n/2元素开始down，最下面一层元素的个数是n/2，其余上面的元素的个数是n/2，从最下面一层到最高层，每层元素的个数是n/2^m【m从下到上，从1计算，m=1时是最下面一层】，时间复杂度就是元素个数*高度【高度从下到上，从0计算】

性质

1.堆是一棵完全二叉树【除叶子结点之外，所有结点都是非空的】

2.小根堆：每个点的值都是小于等于其左右两个儿子的，根结点就是整个数据中的最小值

静态数组存储——一维数组

用一个一维数组来存，根结点放在数组开头，1号点是根结点，结点x的左儿子下标为2x，右儿子下标为2x+1

两个基本操作

对于所有的堆操作而言，每个操作都可以使用这两个操作构建。

down(x) 向下调整——从下往上down一次就变成一个堆

大数位于上面，需要向下移

每次与其两个儿子进行比较，找到较小的儿子与其进行交换，直到小于所有的儿子为止【该结点的子结点都大于该结点】

//递归实现

void down(int u) {

int t = u;//用t表示三个点中的最小值

if (u * 2 <= size1 && h[u * 2] < h[t])//先判断是否有左儿子，然后判断左儿子是否小于其本身,如果成立，交换

t = u * 2;

if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t])//再判断是否有右儿子，然后判断右儿子是否小于其本身,如果成立，交换

t = u * 2 + 1;

//最终，t存的就是三个点中最小的结点编号

if (u != t) {//如果u!=t，说明根结点就不是最小的，需要交换

swap(h[u], h[t]);//交换

down(t);//递归，交换之前h[t]<=h[u]，交换之后h[t]>h[u]，h[t]中存的是大数，对其再进行down操作，即递归

}

return;

}

up(x) 向上调整

小数位于下面，需要向上移

每次只需要与其根结点比较，如果小于其根结点，就与其根结点进行交换，直到>=其根结点为止

//循环实现

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父结点为u/2,父结点存在且大于本身，交换

swap(h[u / 2], h[u]);

u = u / 2;

}

return;

}

操作

【前三最重要】

【下标从1开始】

1.向集合中插入一个数

在整个堆的最后一个位置插入，然后再向上调整

heap[++size]=x;

up(size);

2.求集合中的最小值

heap[1];

3.删除最小值

用整个堆的最后一个元素覆盖掉堆顶的元素，然后size--，然后向下调整

因为删去最后一个结点特别容易，而删除根结点却不易

heap[1]=heap[size];

size--;

down(1);

4.删除任意一个元素

用堆的最后一个结点覆盖该结点，然后size--，然后向下调整（变大）、向上调整（变小），二选一执行

heap[k]=heap[size];

size--;

down(k);//变大

up(k);//变小

5.修改任意一个操作

heap[k]=x;

down(k);//变大

up(k);//变小

例题——堆排序

题目描述

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式

共一行，包含m个整数，表示整数数列中前m小的数。

数据范围

1≤m≤n≤10^5，

1≤数列中元素≤10^9

输入样例

5 3

4 5 1 3 2

输出样例

1 2 3

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 100010;

int n, m;

int h[N], size1;//h[N]就是heap[N],size1存储当前有多少个元素

int main() {

scanf("%d%d", &n, &m);

for (int i = 1;i <= n;i++)

scanf("%d", &h[i]);

size1 = n;

//将数组建成堆 <O(n)

for (int i = n / 2;i;i--) //从n/2开始down

down(i);

while (m--) {

printf("%d ", h[1]);//每次输出堆顶元素，并将其删去

h[1] = h[size1];

size1--;

down(1);

}

return 0;

}

例题——模拟堆[包含映射]

增加两个数组

使用两个数组维护两个映射关系，ph[k] 存第k个插入的点在堆中的下标，hp[k] 存堆中下标为k的点是第几个插入的点

增加的原因

因为按第几个插入元素更改内容，需要知道第i个插入的元素在堆中的下标，所以需要ph的存在，而因为元素在进行down与up操作时，使得ph内容与实际堆的元素不对应，所以要改变ph，而改变ph应该知道，每一个下标对应的插入元素是第几个，所以需要hp的存在。每次交换位置时应该共同维护这两个数组。

交换操作

void heap_swap(int a, int b) {

swap(ph[hp[a]], ph[hp[b]]);//交换指向

swap(hp[a], hp[b]);

swap(h[a], h[b]);

return;

}

交换堆中的两个元素时，hp 和 ph 也改变。先改变 hp 和 ph 中的内容，然后改变这两个结点中的值。先根据交换的下标找到对应的 hp，并以两个 hp 元素值作为 ph 的下标，交换这2个 ph 元素值。之后根据下标交换 hp。

swap(ph[hp[a]], ph[hp[b]])；为什么这里的ph的下标是hp的元素值而不是堆中元素的编号？

因为ph的下标k的含义【即ph[k]的k的含义】是第k个插入的点，所以我们要找到第k个插入的点而不是堆中下标为k的点。

改变后的操作

up 操作

手写的heap_swap函数代替原来的swap函数

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父结点为u/2,父结点存在且大于本身，交换

heap_swap(u / 2, u);

u = u / 2;

}

return;

}

down 操作

手写的heap_swap函数代替原来的swap函数

void down(int u) {

int t = u;//用t表示三个点中的最小值

if (u * 2 <= size1 && h[u * 2] < h[t])//先判断是否有左儿子，然后判断左儿子是否小于其本身,如果成立，交换

t = u * 2;

if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t])//再判断是否有右儿子，然后判断右儿子是否小于其本身,如果成立，交换

t = u * 2 + 1;

//最终，t存的就是三个点中最小的结点编号

if (u != t) {//如果u!=t，说明根结点就不是最小的，需要交换

heap_swap(u, t);//交换

down(t);

}

return;

}

向集合中插入一个数

添加hp和ph数组中的映射关系

scanf("%d", &x); //向堆中插入x

size1++;

m++;

ph[m] = size1;

hp[size1] = m;

h[size1] = x;

up(size1);

输出集合中的最小值

printf("%d\n", h[1])

删除最小值

手写的heap_swap函数代替原来的swap函数

heap_swap(1, size1);

size1--;

down(1);

删除第k个插入的元素

scanf("%d", &k);//输入k

k = ph[k];//找到第k个插入的元素在堆中的下标，然会对其进行删除

heap_swap(k, size1);//用堆中最后一个元素覆盖找到的元素，然会进行调整

size1--;

down(k), up(k);

修改第k个插入的元素

scanf("%d%d", &k, &x);//输入k和修改后的值x

k = ph[k];//找到第k个插入的元素在堆中的下标，然后修改其值，修改后进行调整

h[k] = x;

down(k), up(k);

题目描述

维护一个集合，初始时集合为空，支持如下几种操作：

“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≤10^5

−10^9≤x≤10^9

数据保证合法。

输入样例

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 h[N], ph[N], hp[N], size1;//h[N]就是heap[N],size1存储当前有多少个元素,ph[k]存第k个插入数组的下标

//ph[j]=k【第j次插入数组的数的下标是k】,hp[k]=j【下标为k的数是第j次插入数组中的数】

void heap_swap(int a, int b) {

swap(ph[hp[a]], ph[hp[b]]);//交换指向

swap(hp[a], hp[b]);

swap(h[a], h[b]);

return;

}

void down(int u) {

int t = u;//用t表示三个点中的最小值

if (u * 2 <= size1 && h[u * 2] < h[t])//先判断是否有左儿子，然后判断左儿子是否小于其本身,如果成立，交换

t = u * 2;

if (u * 2 + 1 <= size1 && h[u * 2 + 1] < h[t])//再判断是否有右儿子，然后判断右儿子是否小于其本身,如果成立，交换

t = u * 2 + 1;

//最终，t存的就是三个点中最小的结点编号

if (u != t) {//如果u!=t，说明根结点就不是最小的，需要交换

heap_swap(u, t);//交换

down(t);

}

return;

}

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父结点为u/2,父结点存在且大于本身，交换

heap_swap(u / 2, u);

u = u / 2;

}

return;

}

int main() {

int n, m = 0;

scanf("%d", &n);

while (n--) {

char op[10];

int k, x;

scanf("%s", op);

if (!strcmp(op, "I")) {

scanf("%d", &x);

size1++;

m++;

ph[m] = size1;

hp[size1] = m;

h[size1] = x;

up(size1);

}

else if (!strcmp(op, "PM"))

printf("%d\n", h[1]);

else if (!strcmp(op, "DM")) {

heap_swap(1, size1);

size1--;

down(1);

}

else if (!strcmp(op, "D")) {

scanf("%d", &k);

k = ph[k];

heap_swap(k, size1);

size1--;

down(k), up(k);

}

else {

scanf("%d%d", &k, &x);

k = ph[k];

h[k] = x;

down(k), up(k);

}

}

return 0;

}