堆

思路

堆的原理就是每個節點儲存以自身為根的樹的最值。

那麼左右子樹，根節點也有此性質。

由此，較難的點便是插入與删除的樹的調整。

# include <cstdio>
# include <iostream>
using namespace std;
# define INF    0x3f3f3f3f3f3f3f3f
# define MX     200005
/**************************/
int n;
int heap[MX];

void init() {
    n = 0;
}

/// 節點向上調整
void up(int u) {
    while(u>1 && heap[u] < heap[u/2]) {
        swap(heap[u], heap[u/2]);
        u/=2;
    }
}

/// 節點向下調整
void down(int u) {
    while(u<=n) {
        if (u*2+1<=n) { //有左右孩子
            int small = heap[u*2]<heap[u*2+1] ? u*2:u*2+1;  // 找出孩子中較小的
            if (heap[small] < heap[u]) {
                swap(heap[small], heap[u]);
                u = small;
            } else break;
        } else if (u*2<=n && heap[u*2] < heap[u]) { //隻有左孩子
            swap(heap[u*2], heap[u]);
            u = u*2;
        } else break;
    }
}

/// 增加資料
void add(int x){
    heap[++n] = x;
    up(n);
}

/// 删除資料
int dele() {
    if (n==0) return -1;

    int ret = heap[1];
    swap(heap[n--], heap[1]); // 将根節點與末節點的值互換，并且n--
    down(1);
    return ret;
}


int main() {
    init();

    int xxx[98] = {-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39};

    for (int i=0; i<98; i++) {
        add(xxx[i]);
    }

    for (int i=0; i<98; i++){
        printf("%d\n", dele());
    }
}