求解第K大元素,第K小元素/前k大元素,前k小元素/中位数 (堆·二叉堆) poj1442/black box

如何求解一个第k大元素or第k小元素问题呢?/前k大元素or前k小元素

• • 这类问题通常会有两种情况,1· 有序数组求解第k大, 2·无序数组(前k小or前k大)

这类问题通常会有两种情况,1· 有序数组求解第k大, 2·无序数组(前k小or前k大)

通常对于第k大元素问题求解过程如下:

1·我们只需要用一个小顶堆

2·从数组中选择k个元素,加入堆中…按顺序加入即可,最小的元素一定是堆顶元素.

3·数组中剩下的元素依次与堆顶比较.(我们需维护小顶堆)

4·堆顶元素就是第k大堆元素

举例 1 2 3 4 5 求解第3大元素,我们只需要维护 有3个元素堆小顶堆.我们直观的看 第三大的就是3.

一开始将 1 2 3 加入堆中,1在堆顶.

第一轮 1 与 4 比较,大于堆顶元素则1出堆,4入堆 此时 堆顶为2

第二轮 2 与 5比较 同上 堆顶被调整为3

3便是我们需要的答案

第k小元素反之亦然,换成大顶堆

前k大元素 or 前k小元素

如果我们单一的用一个大顶堆或者一个小顶堆,难以解决这类问题

我们可以将这类问题 抽象成 求一个数组里的中位数问题

假设给一个数组 在此借用POJ1442 的Black Box 题目

大概解释一下,输入了n个数,m次询问.m次询问就是让我们求前m个元素中,第m小的元素

如果只用一个堆,是没有办法做解决的

所以我们需要使用二叉堆(对顶堆)

所有小堆元素 > 大堆元素,即可在大堆的堆顶找到第m小的元素

#include <iostream> 
using namespace std;
#include <set>
#define MAX 30000
int val[MAX+5] ={0};
typedef pair <int ,int> PII;
set<PII> s1,s2;
int main() {
    int n;
    int m;
    cin >> n>> m;
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    for(int i = 1, j = 0; i <= m; i++) {
        int k;
        cin >> k;
        while ( j < k ) {
            ++j;
            if(s1.size() == 0 || -s1.begin()->first > val[j]){ //
                s1.insert(PII(-val[j],j));
            }else {
                s2.insert(PII(val[j],j));
            }
        }
        while (s1.size() > i) {
            s2.insert(PII(-s1.begin()->first , s1.begin()->second));
            s1.erase(s1.begin());
        }
        while (s1.size() < i) {
            s1.insert(PII(-s2.begin()->first , s2.begin()->second));
            s2.erase(s2.begin());
        }
        cout << -(s1.begin()->first) << endl;
    }
    return 0;
}