minmaxheap.cpp

Bài toán

Xây dựng Min-max heap (hay còn gọi là priority queue hai đầu)

Cho một hàng đợi, có các thao tác : thêm một số vào hàng đợi (push), lấy và in ra số bé nhất (pop_front), lấy và in ra số lớn nhất (pop_back). Sau khi pop_front, pop_back, các phần tử được pop bị loại khỏi hàng đợi.

Độ phức tạp

chèn : O(logn)

xóa : O(logn)

đọc số lớn nhất : O(1)

đọc số bé nhất : O(1)

bộ nhớ : O(n) với n là chiều dài lớn nhất của hàng đợi

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

inline int level(int u){

    for (int i=1; u&u+1; i+=i) u|=(u>>i);

    return __builtin_popcount(u);

}

struct min_max_heap {

    ii T[1230997];

    int n;

    bool adjacent_exchange(int u, int v){

        if (T[u]<T[v] xor level(u)&1) swap(T[u], T[v]);

        else return false;

        return true;

    }

    bool discrete_exchange(int u, int v){

        if (T[u]>T[v] xor level(u)&1) swap(T[u], T[v]);

        else return false;

        return true;

    }

    bool exchange(int u, int v){

        if (u<1 || u>n || v<1 || v>n || T[u]==T[v]) return false;

        int x = level(u), y = level(v);

        if (abs(x-y)>2 || x==y) { printf("Fatal\n"); return false; }

        if (x&1 xor y&1) return adjacent_exchange(u, v);

        else return discrete_exchange(u, v);

    }

    int potential(int u){

        int v, r=0;

        for (v=u*4; v<=u*4+3 && v<=n; v++)

        if ((T[v]>=T[r] xor level(u)&1) || r==0) r=v;

        for (v=u*2; v<=u*2+1 && v<=n; v++) // Very important

        if ((T[v]>=T[r] xor level(u)&1) || r==0) r=v;

        return r;

    }

    void push(ii x){

        int u = ++n;

        T[u] = x;

        if (exchange(u, u/2)) u=u/2;

        while (exchange(u, u/4)) u=u/4;

    }

    void pop(int u){

        if (u==0 || n==0) return;

        T[u]=T[n--];

        int v = potential(u);

        while (exchange(v, u)) {

            exchange(v, v/2); // Very important

            u=v; v=potential(u);

        }

        exchange(u*2, u);

        exchange(u*2+1, u);

    }

    int i_back(){

        int r=0;

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

        if (T[i]>T[r] || r==0) r=i;

        return r;

    }

    ii front(){ return T[1]; }

    ii back(){ return T[i_back()]; }

    void pop_front(){ pop(1); }

    void pop_back(){ pop(i_back()); }

    void show(){

        int i;

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

            for (int j=1<<5-level(i); j>=3; j--) printf(" ");

            if (i&i+1) printf(" %d", T[i]);

            else printf(" %d\n", T[i]);

        }

    }

};

min_max_heap tr;

main(){

    int ch, p, q;

    while (scanf("%d", &ch) > 0){

        if (ch==0) tr.show();

        if (ch==1) {

            scanf("%d%d", &p, &q);

            tr.push(ii(q, p));

        }

        if (ch==2) {

            if (tr.n==0) printf("0\n");

            else {

                printf("%d\n", tr.back().second);

                tr.pop_back();

            }

        }

        if (ch==3) {

            if (tr.n==0) printf("0\n");

            else {

                printf("%d\n", tr.front().second);

                tr.pop_front();

            }

        }

    }

}

Nhận xét

Code này đã được dùng để nộp cho một bài trên SPOJ.