最小堆積的基本操作

題目敘述

請實作一個以整數為元素、可隨時取出最小值的最小堆積（二元堆積，索引從 0 開始），並提供推入、取出、查看、查詢大小與判斷是否為空等操作。

背景

二元堆積把元素放在一個陣列裡，並把它看成一棵完全二元樹，規則是每個父節點都不大於它的子節點。索引 i 的子節點位於 2i+1 與 2i+2，父節點位於 (i−1)/2，所以不需要指標。這樣 push 與 pop 的時間為 O(log Q)，top 為 O(1)。

需要提交的內容

請提交 heap.h 與 heap.c，介面如下：

typedef struct heap heap;

void heap_init(heap *h);
void heap_push(heap *h, int x);
int heap_pop(heap *h); /* remove min (only when non-empty) */
int heap_top(heap *h); /* peek min */
int heap_size(heap *h);
int heap_empty(heap *h);

驅動程式協定

驅動程式先讀入 Q，接著讀入 Q 行操作，每行是 push x、pop、top、size 或 empty 其中之一。

• top、pop、size、empty 各印出一行結果。
• 堆積為空時，pop 與 top 印出 EMPTY。
• empty 在堆積為空時印出 1，否則印出 0。

輸入格式

• 第 1 行：操作數 Q。
• 接下來 Q 行：一個操作。

輸出格式

每個會產生輸出的操作印出一行，規則見上。

限制

• 1 ≤ Q ≤ 5 · 10⁵
• 數值落在 [−10⁶, 10⁶]

範例

範例 1

輸入

5
push 3
push 1
push 2
top
pop

輸出

1
1

推入 3、1、2 後，最小的是 1。top 只查看不移除，印出 1；pop 取出同一個最小值，也印出 1。

範例 2

輸入

4
push 5
pop
pop
empty

輸出

5
EMPTY
1

第一個 pop 取出唯一的 5。第二個 pop 遇到空堆積，印出 EMPTY。最後 empty 確認堆積已空，印出 1。

範例 3

輸入

2
top
pop

輸出

EMPTY
EMPTY

堆積從未放入任何元素，所以 top 與 pop 都要印出 EMPTY，不能當機，也不能印出隨機的數字。

範例 4

輸入

6
push 10
push 10
size
pop
pop
empty

輸出

2
10
10
1

兩個 10 是兩個獨立的元素：size 印出 2，兩次 pop 都成功之後堆積才變空。

範例 5

輸入

7
push -5
push -5
push 0
top
pop
top
size

輸出

-5
-5
-5
2

負數照一般整數比大小，-5 < 0，所以兩次查詢的最小值都是 -5。取出一個 -5 之後，堆積還剩 -5 與 0 兩個元素。

範例 6

輸入

1
empty

輸出

1

新堆積上直接查詢 empty，印出 1。

說明

• 把堆積存在動態陣列裡。push 先放在尾端再往上調整；pop 把根與最後一個元素交換、縮小陣列，再把新的根往下調整。
• 空堆積不可讀取未初始化的記憶體。
• 每個操作必須在 O(log Q) 內完成，否則壓力測資會逾時。