M04078: 实现堆结构

http://cs101.openjudge.cn/practice/04078/

要求手搓堆实现。

思路：根据课上所讲直接写即可，用时约20min

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : value(v), left(nullptr), right(nullptr) {}
    TreeNode(int v, TreeNode* l, TreeNode* r) : value(v), left(l), right(r) {}
};
class quque//手搓最小堆
{
    public:
        vector<int> q;
        void push(int value)
        {
            q.push_back(value);
            int i = q.size()-1;
            while (i > 0)
            {
                int parent = (i-1)/2;
                if (q[parent] > q[i])
                {
                    int tmp = q[parent];
                    q[parent] = q[i];
                    q[i] = tmp;
                    i = parent;
                }
                else
                    break;
            }
        }
        void pop()
        {
            q[0] = q[q.size()-1];
            q.pop_back();
            int i = 0;
            while (2 * i + 1 < q.size())
            {
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                int min = left;
                if (right < q.size() && q[right] < q[left])
                    min = right;
                if (q[min] < q[i])
                {
                    int tmp = q[min];
                    q[min] = q[i];
                    q[i] = tmp;
                    i = min;
                }
                else
                    break;
            }
        }
        int top()
        {
            return q[0];
        }
};
int main() 
{
    int n;
    cin >> n;
    quque q;
    while (n--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int value;
            cin >> value;
            q.push(value);

        }
        else
        {
            cout << q.top() << endl;
            q.pop();
        }
    }
    return 0;
}