heap

题目描述
实现一个小根堆用以做优先队列。
给定如下数据类型的定义：

class array {
 private:
 int elem[MAXN];
 public:
 int &operator[](int i) { return elem[i]; }
};
class heap {
 private:
 int n;
 array h;
 public:
 void clear() { n = 0; }
 int top() { return h[1]; }
 int size() { return n; }
 void push(int);
 void pop();
};

要求实现：

void heap::push(int x) {
 // your code
}
void heap::pop() {
 // your code
}

测试样例
test code

heap h;
h.push(3);
h.push(1);
h.push(2);
printf("%d\n", h.top());
h.pop();
printf("%d\n", h.top());

test output

1
2

提示
只提交heap::push和heap::pop，注意堆顶元素的下标是1而不是0。
Yizuodi的答案
参考：小根堆(Heap)的详细实现

#include <iostream>
#include <heap.h>
using namespace std;

void heap::push(int x)
{
    ++n;//heap size+1
    h[n] = x;
    int p = n / 2, t = n;
    while (p >= 1)
    {
        if (h[p] <= h[t])
        {
            break;
        }
        swap(h[p], h[t]);
        t = p;
        p = p / 2;
    }
}

void heap::pop()
{
    h[1] = h[n];
    --n;//heap size-1
    int p = 1;//p position
    while (1)
    {
        if (2 * p > n)
            break;
        if (2 * p == n && h[p] <= h[n])
            break;
        if (2 * p < n && h[p] <= h[p * 2] && h[p] <= h[p * 2 + 1])
            break;
        if (2 * p == n && h[p] > h[n])
        {
            swap(h[n], h[p]);
            break;
        }
        else
        {
            if (h[p * 2] < h[p * 2 + 1])
            {
                swap(h[p], h[p * 2]);
                p = p * 2;
            }
            else
            {
                swap(h[p], h[p * 2 + 1]);
                p = p * 2 + 1;
            }
        }
    }
}