hiho 學習日記：hiho一下第二十八周 （堆）

http://hihocoder.com/contest/hiho28/problem/1

堆的形狀是一個完全二叉樹，對于最大堆任意根的權值大于左右孩子的權值，而最小堆的任意根的權值小于左右孩子的權值

這裡示範的是最大堆

當插入一個值的時候，把這個值添加到堆尾中，然後向上調整

void up(int p) {
    int q = p/2;//目前節點尾p，父節點尾q
    int a = Heap[p];//目前節點的值
    while(q >= 1 && a > Heap[q]) {//如果父節點的值小于目前的值，就交換
        Heap[p] = Heap[q];
        p = q;
        q = p/2;
    }
    Heap[p] = a;
}

void insert(int a) {
    Heap[++hlength] = a;
    up(hlength);
}
           

删除堆頂的值的時候，把堆尾的元素指派給堆頂，然後向下調整

void down(int p) {
    int q = p * 2;
    int a = Heap[p];
    while(q <= hlength) {
        if(q < hlength && Heap[q] < Heap[q + 1]) q ++;//找到左右孩子的最大值
        if(Heap[q] <= a) break;
        else {
            Heap[p] = Heap[q];
            p = q;
            q = p * 2;
        }
    }
    Heap[p] = a;
}

int getMax() {
    int r = Heap[1];
    Heap[1] = Heap[hlength --];
    down(1);
    return r;
}


           

AC代碼：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define LL long long

int Heap[maxn];
int hlength;

void down(int p) {
    int q = p * 2;
    int a = Heap[p];
    while(q <= hlength) {
        if(q < hlength && Heap[q] < Heap[q + 1]) q ++;//找到左右孩子的最大值
        if(Heap[q] <= a) break;
        else {
            Heap[p] = Heap[q];
            p = q;
            q = p * 2;
        }
    }
    Heap[p] = a;
}

void up(int p) {
    int q = p/2;
    int a = Heap[p];
    while(q >= 1 && a > Heap[q]) {
        Heap[p] = Heap[q];
        p = q;
        q = p/2;
    }
    Heap[p] = a;
}

void insert(int a) {
    Heap[++hlength] = a;
    up(hlength);
}

int getMax() {
    int r = Heap[1];
    Heap[1] = Heap[hlength --];
    down(1);
    return r;
}

int main()
{
    hlength = 0;
    int T;
    scanf("%d", &T);
    while(T --) {
        char c[5];
        int value;
        scanf("%s", c);
        if(c[0] == 'A') {
            scanf("%d", &value);
            insert(value);
        }
        else
            cout << getMax() << endl;
    }
    return 0;
}