Algorithm11.2 数据结构堆

[TOC]

数据结构堆 & 手写堆

堆：

分类：最大堆、最小堆

过程：首先按照完全二叉树的形式，将序列填补到初始的堆中

（堆-附加：利用堆的性质来判断是否是堆：「PAT1147」，判断方法就是直接对给定的层次遍历的序列来判断，是否满足a[i] > a[2<<i] && a[i] > a[2<<i|1]或者a[i] < a[2<<i] && a[i] < a[2<<i|1] ，来查看是否是最大堆或者最小堆

用到堆优化的思路不一定是用堆，也可能是通过利用优先队列进行优化【堆的优化的应用场景：解决重复排序问题，每添加一个新的元素【在线更新】，都要重新排一次序 => 可以用堆进行优化】

用到堆的方式：

手写堆：「例如下面的P3378手写堆 // P1631RMQ问题」的up/down方法来维护堆

直接利用优先队列来优化复杂度，优化的方式就是直接拿堆顶，进而取堆顶得到最大最小或者堆结构带来的排序「P2085取前最小」的每次拿堆顶，然后在线插入新的元素之后重新自动排序获取下一次的堆顶。

判断堆是否为最大堆、最小堆

https://pintia.cn/problem-sets/994805342720868352/problems/994805342821531648

1、判断是否是最大堆最小堆：直接判断父节点与两个子节点的的大小关系。

可以通过维护两个变量is_max = 1 / is_min = 1，当存在有子节点小于父节点=>不满足最小堆了把is_min = 0；当存在有子节点大于父节点=>不满足最小堆了把is_max = 0

最后看is_max和is_min两个变量，是否是最大最小堆。

// 从底部往上遍历
for (int j = 2; j <= m; ++j) {
    if (a[j] > a[j/2]) is_big = 0;
    else is_small = 0;
}

https://www.luogu.com.cn/problem/P3378

手写堆实现获取区间前几大/最大

1、数据结构：一个模拟堆的数组myheap

2、堆的基本操作：

insert：插入新的元素
myheap[1]：获取堆顶元素
deletetop：删除堆顶元素

3、【下面范例都是小顶堆】

插入新的元素 => 从堆底往堆顶移动索引

while (idx > 1) {
  if (myheap[idx] < myheap[idx>>1]) {
    swap(myheap[idx], myheap[idx>>1]);
    idx >>= 1;
  }
}

删除堆顶元素 => 从堆顶网堆底移动索引

int son = idx<<1;
while (son <= size) {
  if (son < size && myheap[son] > myheap[son+1]) son++;
  if (myheap[son] < myheap[idx]) {
    swap(myheap[son], myheap[idx]);
    idx <<= 1;
  }
}

完整代码：

#include <iostream>
using namespace std;
#define maxn 1000010
int t, myheap[maxn], size, tp, ta;

void up(int idx) {
    while (idx > 1) {
        if (myheap[idx] < myheap[idx>>1]) {
            swap(myheap[idx], myheap[idx>>1]);
            idx >>= 1;
        } else break;
    }
}

void insert(int x) {
    myheap[++size] = x;
    up(size);
}

void down(int idx) {
    int son = idx<<1;
    while (son <= size) {
        if (son < size && myheap[son] > myheap[son+1]) son++;
        if (myheap[son] < myheap[idx]) {
            swap(myheap[son], myheap[idx]);
            idx = son; son <<= 1;
        } else break;
    }
}

void deletetop() {
    myheap[1] = myheap[size--];
    down(1);
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &tp);
        if (tp == 1) {
            scanf("%d", &ta);
            insert(ta);
        } else if (tp == 2) printf("%d\n", myheap[1]);
        else deletetop();
    }
    return 0;
}

用STL库中的堆

用优先队列模拟堆的最大

声明一个小顶堆即可。priority_queue<int, vector<int>, greater<int>> pq;

#include <iostream>
using namespace std;
#include <queue>
priority_queue<int, vector<int>, greater<int>> pq;
int m, op, t;

int main() {
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &op);
        switch (op) {
            case 1: scanf("%d", &t);pq.push(t);break;
            case 2: printf("%d\n", pq.top());break;
            case 3: pq.pop();break;
        }
    }
    return 0;
}

限定长度的堆 => 类似于滑动窗口

(RMQ问题，也可用于解决类似于滑动窗口，单调队列)

https://www.luogu.com.cn/problem/P1631

1、注意：选取最小的几个的话，不能用最小堆，需要用最大堆，然后每次再来新的元素之后，判断此元素和堆顶的大小关系：如果大于堆顶=>直接忽略；小于堆顶，把堆顶替换，然后往下down即可。

#include <iostream>
using namespace std;
#define maxn 100010
int n, myheap[maxn], size, a[maxn], b[maxn], ans[maxn];

void up(int idx) {
    while (idx > 1) {
        if (myheap[idx] > myheap[idx>>1]) {
            swap(myheap[idx], myheap[idx>>1]);
            idx >>= 1;
        } else break;
    }
}

void insert(int x) {
    myheap[++size] = x;
    up(size);
}

void down(int idx) {
    int son = idx<<1;
    while (son <= size) {
        if (son<size && myheap[son]<myheap[son+1]) son++;
        if (myheap[idx] < myheap[son]) {
            swap(myheap[idx], myheap[son]);
            idx=son;son<<=1;
        } else break;
    }
}

void deletetop(){
    myheap[1] = myheap[size--];
    down(1);
}

void change(int x) {
    myheap[1] = x;
    down(1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i) insert(a[1]+b[i]);
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (a[i] + b[j] > myheap[1]) break;
            change(a[i]+b[j]);
        }
    for (int i = 1; i <= n; ++i) {
        ans[i] = myheap[1];
        deletetop();
    }
    for (int i = n; i >= 1; --i) printf("%d ", ans[i]);
    return 0;
}

取前最小 - 复杂的题意

https://www.luogu.com.cn/problem/P2085

1、最小值可能是某一个函数一直往后取x，也有可能是不同的函数各自往后延伸，因此至于延伸哪个，每次都要排序，然后在线排序 => 堆型数据结构优化

2、用结构体来储存每个单元，然后在每次优先队列取top的，留下id和xx的值，然后往后拓展。

#include <iostream>
using namespace std;
#define maxn 10010
struct node {
    int val, id, xx;
    node(int val, int id, int xx): val(val), id(id), xx(xx){}
    bool operator < (const node n) const {return val > n.val;}
};
int n, m, a[maxn], b[maxn], c[maxn];
#include <queue>
priority_queue<node, vector<node>, less<node>> pq;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        pq.push(node(a[i]+b[i]+c[i], i, 1));
    }
    for (int i = 1; i <= m; ++i) {
        node nw = pq.top();pq.pop();
        printf("%d ", nw.val);
        int nid = nw.id, nxx = nw.xx+1;
        pq.push(node(a[nid]*nxx*nxx+b[nid]*nxx+c[nid], nid, nxx));
    }
    return 0;
}

Posted on Feb 1, 2021

Algorithm11.2 数据结构 堆

数据结构 堆 & 手写堆