手寫堆，而非stl中的堆

如何手寫一個(gè)堆？

//將數(shù)組建成堆 <O(n)

for (int i = n / 2;i;i--) //從n/2開(kāi)始down

down(i);

從n/2元素開(kāi)始down，最下面一層元素的個(gè)數(shù)是n/2，其余上面的元素的個(gè)數(shù)是n/2，從最下面一層到最高層，每層元素的個(gè)數(shù)是n/2^m【m從下到上，從1計(jì)算，m=1時(shí)是最下面一層】，時(shí)間復(fù)雜度就是元素個(gè)數(shù)*高度【高度從下到上，從0計(jì)算】

性質(zhì)

1.堆是一棵完全二叉樹(shù)【除葉子結(jié)點(diǎn)之外，所有結(jié)點(diǎn)都是非空的】

2.小根堆：每個(gè)點(diǎn)的值都是小于等于其左右兩個(gè)兒子的，根結(jié)點(diǎn)就是整個(gè)數(shù)據(jù)中的最小值

靜態(tài)數(shù)組存儲(chǔ)——一維數(shù)組

用一個(gè)一維數(shù)組來(lái)存，根結(jié)點(diǎn)放在數(shù)組開(kāi)頭，1號(hào)點(diǎn)是根結(jié)點(diǎn)，結(jié)點(diǎn)x的左兒子下標(biāo)為2x，右兒子下標(biāo)為2x+1

兩個(gè)基本操作

對(duì)于所有的堆操作而言，每個(gè)操作都可以使用這兩個(gè)操作構(gòu)建。

down(x) 向下調(diào)整——從下往上down一次就變成一個(gè)堆

大數(shù)位于上面，需要向下移

每次與其兩個(gè)兒子進(jìn)行比較，找到較小的兒子與其進(jìn)行交換，直到小于所有的兒子為止【該結(jié)點(diǎn)的子結(jié)點(diǎn)都大于該結(jié)點(diǎn)】

//遞歸實(shí)現(xiàn)

void down(int u) {

int t = u;//用t表示三個(gè)點(diǎn)中的最小值

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存的就是三個(gè)點(diǎn)中最小的結(jié)點(diǎn)編號(hào)

if (u != t) {//如果u!=t，說(shuō)明根結(jié)點(diǎn)就不是最小的，需要交換

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

down(t);//遞歸，交換之前h[t]<=h[u]，交換之后h[t]>h[u]，h[t]中存的是大數(shù)，對(duì)其再進(jìn)行down操作，即遞歸

}

return;

}

up(x) 向上調(diào)整

小數(shù)位于下面，需要向上移

每次只需要與其根結(jié)點(diǎn)比較，如果小于其根結(jié)點(diǎn)，就與其根結(jié)點(diǎn)進(jìn)行交換，直到>=其根結(jié)點(diǎn)為止

//循環(huán)實(shí)現(xiàn)

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父結(jié)點(diǎn)為u/2,父結(jié)點(diǎn)存在且大于本身，交換

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

u = u / 2;

}

return;

}

操作

【前三最重要】

【下標(biāo)從1開(kāi)始】

1.向集合中插入一個(gè)數(shù)

在整個(gè)堆的最后一個(gè)位置插入，然后再向上調(diào)整

heap[++size]=x;

up(size);

2.求集合中的最小值

heap[1];

3.刪除最小值

用整個(gè)堆的最后一個(gè)元素覆蓋掉堆頂?shù)脑?#xff0c;然后size--，然后向下調(diào)整

因?yàn)閯h去最后一個(gè)結(jié)點(diǎn)特別容易，而刪除根結(jié)點(diǎn)卻不易

heap[1]=heap[size];

size--;

down(1);

4.刪除任意一個(gè)元素

用堆的最后一個(gè)結(jié)點(diǎn)覆蓋該結(jié)點(diǎn)，然后size--，然后向下調(diào)整（變大）、向上調(diào)整（變小），二選一執(zhí)行

heap[k]=heap[size];

size--;

down(k);//變大

up(k);//變小

5.修改任意一個(gè)操作

heap[k]=x;

down(k);//變大

up(k);//變小

例題——堆排序

題目描述

輸入一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列，從小到大輸出前m小的數(shù)。

輸入格式

第一行包含整數(shù)n和m。

第二行包含n個(gè)整數(shù)，表示整數(shù)數(shù)列。

輸出格式

共一行，包含m個(gè)整數(shù)，表示整數(shù)數(shù)列中前m小的數(shù)。

數(shù)據(jù)范圍

1≤m≤n≤10^5，

1≤數(shù)列中元素≤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存儲(chǔ)當(dāng)前有多少個(gè)元素

int main() {

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

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

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

size1 = n;

//將數(shù)組建成堆 <O(n)

for (int i = n / 2;i;i--) //從n/2開(kāi)始down

down(i);

while (m--) {

printf("%d ", h[1]);//每次輸出堆頂元素，并將其刪去

h[1] = h[size1];

size1--;

down(1);

}

return 0;

}

例題——模擬堆[包含映射]

增加兩個(gè)數(shù)組

使用兩個(gè)數(shù)組維護(hù)兩個(gè)映射關(guān)系，ph[k] 存第k個(gè)插入的點(diǎn)在堆中的下標(biāo)，hp[k] 存堆中下標(biāo)為k的點(diǎn)是第幾個(gè)插入的點(diǎn)

增加的原因

因?yàn)榘吹趲讉€(gè)插入元素更改內(nèi)容，需要知道第i個(gè)插入的元素在堆中的下標(biāo)，所以需要ph的存在，而因?yàn)樵卦谶M(jìn)行down與up操作時(shí)，使得ph內(nèi)容與實(shí)際堆的元素不對(duì)應(yīng)，所以要改變ph，而改變ph應(yīng)該知道，每一個(gè)下標(biāo)對(duì)應(yīng)的插入元素是第幾個(gè)，所以需要hp的存在。每次交換位置時(shí)應(yīng)該共同維護(hù)這兩個(gè)數(shù)組。

交換操作

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;

}

交換堆中的兩個(gè)元素時(shí)，hp 和 ph 也改變。先改變 hp 和 ph 中的內(nèi)容，然后改變這兩個(gè)結(jié)點(diǎn)中的值。先根據(jù)交換的下標(biāo)找到對(duì)應(yīng)的 hp，并以兩個(gè) hp 元素值作為 ph 的下標(biāo)，交換這2個(gè) ph 元素值。之后根據(jù)下標(biāo)交換 hp。

swap(ph[hp[a]], ph[hp[b]])；為什么這里的ph的下標(biāo)是hp的元素值而不是堆中元素的編號(hào)？

因?yàn)閜h的下標(biāo)k的含義【即ph[k]的k的含義】是第k個(gè)插入的點(diǎn)，所以我們要找到第k個(gè)插入的點(diǎn)而不是堆中下標(biāo)為k的點(diǎn)。

改變后的操作

up 操作

手寫的heap_swap函數(shù)代替原來(lái)的swap函數(shù)

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父結(jié)點(diǎn)為u/2,父結(jié)點(diǎn)存在且大于本身，交換

heap_swap(u / 2, u);

u = u / 2;

}

return;

}

down 操作

手寫的heap_swap函數(shù)代替原來(lái)的swap函數(shù)

void down(int u) {

int t = u;//用t表示三個(gè)點(diǎn)中的最小值

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存的就是三個(gè)點(diǎn)中最小的結(jié)點(diǎn)編號(hào)

if (u != t) {//如果u!=t，說(shuō)明根結(jié)點(diǎn)就不是最小的，需要交換

heap_swap(u, t);//交換

down(t);

}

return;

}

向集合中插入一個(gè)數(shù)

添加hp和ph數(shù)組中的映射關(guān)系

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

size1++;

m++;

ph[m] = size1;

hp[size1] = m;

h[size1] = x;

up(size1);

輸出集合中的最小值

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

刪除最小值

手寫的heap_swap函數(shù)代替原來(lái)的swap函數(shù)

heap_swap(1, size1);

size1--;

down(1);

刪除第k個(gè)插入的元素

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

k = ph[k];//找到第k個(gè)插入的元素在堆中的下標(biāo)，然會(huì)對(duì)其進(jìn)行刪除

heap_swap(k, size1);//用堆中最后一個(gè)元素覆蓋找到的元素，然會(huì)進(jìn)行調(diào)整

size1--;

down(k), up(k);

修改第k個(gè)插入的元素

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

k = ph[k];//找到第k個(gè)插入的元素在堆中的下標(biāo)，然后修改其值，修改后進(jìn)行調(diào)整

h[k] = x;

down(k), up(k);

題目描述

維護(hù)一個(gè)集合，初始時(shí)集合為空，支持如下幾種操作：

“I x”，插入一個(gè)數(shù)x；

“PM”，輸出當(dāng)前集合中的最小值；

“DM”，刪除當(dāng)前集合中的最小值（當(dāng)最小值不唯一時(shí)，刪除最早插入的最小值）；

“D k”，刪除第k個(gè)插入的數(shù)；

“C k x”，修改第k個(gè)插入的數(shù)，將其變?yōu)閤；

現(xiàn)在要進(jìn)行N次操作，對(duì)于所有第2個(gè)操作，輸出當(dāng)前集合的最小值。

輸入格式

第一行包含整數(shù)N。

接下來(lái)N行，每行包含一個(gè)操作指令，操作指令為”I x”，”PM”，”DM”，”D k”或”C k x”中的一種。

輸出格式

對(duì)于每個(gè)輸出指令“PM”，輸出一個(gè)結(jié)果，表示當(dāng)前集合中的最小值。

每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍

1≤N≤10^5

?10^9≤x≤10^9

數(shù)據(jù)保證合法。

輸入樣例

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存儲(chǔ)當(dāng)前有多少個(gè)元素,ph[k]存第k個(gè)插入數(shù)組的下標(biāo)

//ph[j]=k【第j次插入數(shù)組的數(shù)的下標(biāo)是k】,hp[k]=j【下標(biāo)為k的數(shù)是第j次插入數(shù)組中的數(shù)】

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表示三個(gè)點(diǎn)中的最小值

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存的就是三個(gè)點(diǎn)中最小的結(jié)點(diǎn)編號(hào)

if (u != t) {//如果u!=t，說(shuō)明根結(jié)點(diǎn)就不是最小的，需要交換

heap_swap(u, t);//交換

down(t);

}

return;

}

void up(int u) {

while (u / 2 && h[u / 2] > h[u]) {//u的父結(jié)點(diǎn)為u/2,父結(jié)點(diǎn)存在且大于本身，交換

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;

}