手写堆(以小根堆为例)

 Algorithm
 

基础准备

一个数据结构

堆其实是一棵完全二叉树，

用一个一维数组保存堆元素，

下标从1开始存（根节点是1），x的左儿子是2x，x的右儿子是2x+1。

1
int h[N], size;

两个关键(heapify堆化)

  • up

    1
    2
    3
    4
    5
    6
    void up(int u) {
        while(u/2 && h[u/2]>h[u]) {
            swap(h[u/2],h[u]);
            u/=2;
        }
    }

  • down

    1
    2
    3
    4
    5
    6
    7
    8
    void down(int u) {
        if(u*2<=size && h[t]>h[u*2]) t=u*2;
        if(u*2+1<=size && h[t]>h[u*2+1]) t=u*2+1;
        if(t!=u) {
            swap(h[t],h[u]);
            down(t);
        }
    }

五个操作

  • 插入一个数

    1
    heap[++size]=x; up(size);

  • 求集合当中的最小值

    1
    heap[1];

  • 删除最小值

    1
    heap[1]=heap[size];size--;down(1);

  • 删除任意一个元素

    1
    heap[k]=heap[size];size--;up(k);down(k);

  • 修改任意一个元素

    1
    heap[k]=x;up(k);down(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

  • 样例解释：

  • 参考代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <iostream>
    #include <algorithm>
    using namespace std;

    const int N=100010;

    int n,m;
    int h[N],size;

    void down(int u) {
    	int t=u;
    	if(u*2<=size && h[t]>h[u*2]) t=u*2;
        if(u*2+1<=size && h[t]<h[u*2+1]) t=u*2+1;
        if(t!=u) {
            swap(h[u],h[t]);
            down(t);
        }
    }

    void up(int u) {
        while(u/2 && h[u/2]>h[u]) {
            swap(h[u/2],h[u]);
            u/=2;
        }
    }

    int main() {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&h[i]);
        size=n;
        
        // 一种建堆方式：从n/2开始down，一直到1，时间复杂度是O(n) 
        for(int i=n/2;i;i--) down(i);
        
        while(m--) {
            printf("%d ",h[1]);
            h[1]=h[size];
            size--;
            down(1);
        }
        return 0;
    }

模拟堆

  • 描述：

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

  1. “I x”，插入一个数x；
  2. “PM”，输出当前集合中的最小值；
  3. “DM”，删除当前集合中的最小值（当最小值不唯一时，删除最早插入的最小值）；
  4. “D k”，删除第k个插入的数；
  5. “C k x”，修改第k个插入的数，将其变为x；

现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

  • 输入：

    第一行包含整数N。
    接下来N行，每行包含一个操作指令，操作指令为“I x”，“PM”，“DM”，“D k”或“C k x”中的一种。

  • 输出：

    对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。
    每个结果占一行。

  • 数据范围：

    $1\le N \le 10^5$

    $-10^9 \le x \le 10^9$

    数据保证合法。

  • 样例输入：

    10
    I -10
    PM
    I -10
    D 1
    C 2 8
    I 6
    PM
    DM

  • 样例输出：

    -10

    6

  • 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 模拟（带映射版的）堆各项操作的模板
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

const int N=100010;

// ph[i]:第i个插入的数在堆中的位置
// hp[i]:堆中第i个位置的数的插入时刻
int h[N],hp[N],ph[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/2]>h[u]) {
        heap_swap(u/2,u);
        u/=2;
    }
}
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);
            size++;
            m++;
            //第m个插入的数在堆的size位置，堆中size位置上的数是第m个插入的数
            ph[m]=size,hp[size]=m;
            
            // 一种建堆方式：一个一个插，时间复杂度是O(nlogn)
            h[size]=x;
            up(size);
        }
        else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
        else if(!strcmp(op,"DM"))
        {
            heap_swap(1,size);
            size--;
            down(1);
        }
        else if(!strcmp(op,"D"))
        {
            scanf("%d",&k);
            k=ph[k];//找到第k个插入的数所对应的堆里面的位置
            heap_swap(k,size);
            size--;
            down(k),up(k);
        }
        else
        {
            scanf("%d%d",&k,&x);
            k=ph[k];
            h[k]=x;
            down(k),up(k);
        }
    }
    return 0;
}
 Previous

Golang Microservice