11215: 【原1215】bernoulli

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1215

Description

实现一棵Bernoulli树。实现下列操作：

1.insert X，将整数X加入优先队列

2.delete，将优先队列中最小值弹出

3.min，输出最小值

初始优先队列为空。

Input Format

第一行含有一个正整数M（1<=M<=20000),代表总的操作数。

以下M行，每行一个操作。

Output Format

对于min操作，输出一个最小值，回车隔开。

Sample Input1

9
insert 6
insert 6
insert 4
delete
min
delete
insert 9
insert 3
min

Sample Output1

6
3

Limit

输入数据保证合法

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/14.
//


#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
    template<typename Item>
    struct greater {
        bool operator()(const Item &a, const Item &b) {
            return a > b;
        }
    };

    template<typename Item>
    struct less {
        bool operator()(const Item &a, const Item &b) {
            return a < b;
        }
    };
}


template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
    Comparator comparator;
    Item *pq;
    int N = 0;
    int maxN;

private:
    bool cmp(int i, int j) {
        return comparator(pq[i], pq[j]);
    }

    void exch(int i, int j) {
        Item item = pq[i];
        pq[i] = pq[j];
        pq[j] = item;
    }

    void resize(int newMaxN) {
        Item *old = pq;
        pq = new Item[newMaxN + 1];
        int length = newMaxN > maxN ? maxN : newMaxN;
        for (int i = 0; i < length; ++i) {
            pq[i] = old[i];
        }
        delete[] old;
    }

    void swim(int k) {
        while (k > 1 && cmp(k, k / 2)) {
            exch(k / 2, k);
            k /= 2;
        }
    }

    void sink(int k) {
        int j;
        while (2 * k <= N) {
            j = 2 * k;
            j += (j < N && cmp(j + 1, j));
            if (cmp(k, j)) break;
            else {
                exch(k, j);
                k = j;
            }
        }
    }


public:
    BPriorityQueue() {
        BPriorityQueue(1);
    }

    BPriorityQueue(int maxN) : maxN(maxN) {
        pq = new Item[maxN + 1];
    }

    BPriorityQueue(const Item *pq, int size) {
        maxN = N = size;
        this->pq = new Item[size];
        for (int i = 1; i <= N; ++i) {
            this->pq[i] = pq[i - 1];
        }
        for (int k = N / 2; k >= 1; --k) {
            sink(k);
        }
    }

    bool isEmpty() {
        return N == 0;
    }

    int size() {
        return N;
    }

    void insert(const Item &item) {
        if (N == maxN)
            resize(2 * N);
        pq[++N] = item;
        swim(N);
    }

    Item pop() {
        if (N <= maxN / 4)
            resize(maxN / 2);
        Item item = pq[1];
        exch(1, N);
        --N;
        sink(1);
        return item;
    }

    const Item &peek() {
        return pq[1];
    }

    virtual ~BPriorityQueue() {
        delete[] pq;
    }
};


#endif //SBL_BPRIORITYQUEUE_H

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    BPriorityQueue<int, bpq::less<int>> pq(N);
    char cmd[10];
    int tmp;
    while (N--) {
        cin >> cmd;
        switch (cmd[0]) {
            case 'i':
                cin >> tmp;
                pq.insert(tmp);
                break;
            case 'd':
                pq.pop();
                break;
            case 'm':
                cout << pq.peek() << '\n';
                break;
        }
    }
    cout << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //反向迭代器
    template <class U>
    class reverse_iterator {
        U val;
        friend reverse_iterator<U> mVector<T>::rbegin();
        friend reverse_iterator<U> mVector<T>::rend();
    public:
        U& base() {
            return val;
        }
        reverse_iterator() = default;
        reverse_iterator(const reverse_iterator<U>& other) {
            val = other.val;
        }
        reverse_iterator(const U& other) {
            val = other;
        }
        reverse_iterator<U>& operator++() {
            --val;
            return *this;
        }
        reverse_iterator<U> operator++(int) {
            reverse_iterator<U> temp(*this);
            --val;
            return temp;
        }
        reverse_iterator<U>& operator--() {
            ++val;
            return *this;
        }
        reverse_iterator<U> operator--(int) {
            reverse_iterator<U> temp(*this);
            ++val;
            return temp;
        }
        bool operator==(const reverse_iterator<U>& other) const {
            return val == other.val;
        }
        bool operator!=(const reverse_iterator<U>& other) const {
            return val != other.val;
        }
        reverse_iterator<U>& operator=(const reverse_iterator<U>& other) {
            val = other.val;
            return *this;
        }
        T& operator*() const {
            return *val;
        }
    };

    reverse_iterator<iterator> rbegin() {
        auto temp = end();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    reverse_iterator<iterator> rend() {
        auto temp = begin();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[--size];
        vector_data[size] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

template <class T>
class myPriorityQueue {
    mVector<T> queueData;
    unsigned int sizeOfQueue = 0;
    bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

    //向下过滤
    void percolateDown(unsigned int pos) {
        while (pos * 2 <= sizeOfQueue) {
            if (pos * 2 + 1 > sizeOfQueue) {
                //交换
                if (cmp(queueData[pos * 2], queueData[pos])) {
                    auto temp = queueData[pos * 2];
                    queueData[pos * 2] = queueData[pos];
                    queueData[pos] = temp;
                }
                break;
            }
            else {
                bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
                if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
                    auto temp = queueData[pos * 2 + minNum];
                    queueData[pos * 2 + minNum] = queueData[pos];
                    queueData[pos] = temp;
                    pos = pos * 2 + minNum;
                }
                else break;
            }
        }
    }

public:
    //构建
    myPriorityQueue() {
        queueData.clear();
        queueData.push_back((T)0);
        sizeOfQueue = 0;
    }

    //compare函数返回父结点a与孩子结点b的关系正确与否
    myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //根据数组建立堆
    void buildHeap(T* eleData, unsigned int eleNum) {
        queueData.clear();
        sizeOfQueue = eleNum;
        queueData.push_back(*new T);
        for (unsigned int i = 1; i <= eleNum; i++)
            queueData.push_back(eleData[i - 1]);
        //向下过滤
        for (unsigned int pos = eleNum / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    //判断是否空
    bool empty() {
        return sizeOfQueue == 0;
    }

    //返回队列大小
    auto size() {
        return sizeOfQueue;
    }

    //入队
    void push(const T & input) {
        sizeOfQueue++;
        queueData.push_back(input);

        //向上过滤
        for (auto i = sizeOfQueue; i > 1; i = i / 2) {
            //判断是否比父结点更小
            if (cmp(queueData[i], queueData[i / 2])) {
                //交换
                auto temp = queueData[i];
                queueData[i] = queueData[i / 2];
                queueData[i / 2] = temp;
            }
            else break;
        }
    }

    //队列最前
    T top() {
        return queueData[1];
    }

    //出队
    T pop() {
        auto temp = queueData[1];
        queueData[1] = queueData[sizeOfQueue--];
        queueData.pop_back();
        percolateDown(1);
        return temp;
    }
};

int main() {
    int M;
    cin >> M;
    myPriorityQueue<int> myQueue;

    for (; M > 0; M--) {
        char temp[100];
        scanf("%s", temp);
        if (strcmp(temp, "insert") == 0) {
            int tempNum;
            scanf("%d", &tempNum);
            myQueue.push(tempNum);
        }
        else if (strcmp(temp, "delete") == 0) {
            if (!myQueue.empty())
                myQueue.pop();
        }
        else {
            printf("%d\n", myQueue.top());
        }
    }

    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

template <class Type>
class priorityQueue {
   private:
    int currentSize;
    Type *array;
    int maxSize;

    void doubleSpace();
    // void buildHeap();
    void percolateDown(int);

   public:
    priorityQueue(int capacity = 20010);
    // priorityQueue(const Type data[],int size);
    ~priorityQueue();
    bool isEmpty() const;
    void enQueue(const Type &x);
    Type deQueue();
    Type getHead() const;
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
    : maxSize(capacity), currentSize(0) {
    array = new Type[capacity];
}

template <class Type>
priorityQueue<Type>::~priorityQueue() {
    delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const {
    return currentSize == 0;
}

template <class Type>
Type priorityQueue<Type>::getHead() const {
    return array[1];
}

template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
    if (currentSize == maxSize - 1) {
        doubleSpace();
    }

    int hole = ++currentSize;
    for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
        array[hole] = array[hole / 2];
    }

    array[hole] = x;
}

template <class Type>
Type priorityQueue<Type>::deQueue() {
    Type minItem;

    minItem = array[1];
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
    int child;
    Type tmp = array[hole];

    for (; hole * 2 <= currentSize; hole = child) {
        child = hole * 2;

        if (child != currentSize && array[child + 1] < array[child]) {
            child++;
        }

        if (array[child] < tmp) {
            array[hole] = array[child];
        } else {
            break;
        }
    }
    array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
    Type *tmp = array;

    maxSize *= 2;

    array = new Type[maxSize];
    for (int i = 0; i < currentSize; i++) {
        array[i] = tmp[i];
    }

    delete[] tmp;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priorityQueue<long long> Bernoulli;
    int m;
    long long x;
    char order[10];

    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> order;

        if (strcmp(order, "insert") == 0) {
            cin >> x;
            Bernoulli.enQueue(x);
        } else if (strcmp(order, "delete") == 0) {
            Bernoulli.deQueue();
        } else if (strcmp(order, "min") == 0) {
            if (!Bernoulli.isEmpty()) {
                cout << Bernoulli.getHead() << '\n';
            }
        }
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <string>
#include <stack>
#include <cstring>

using namespace std;

template<typename T>
struct Heap {
    T *data;
    int cap, len;

    Heap(int cap = 1024) : cap(cap + 1), len(0) {
        data = new T[cap];
    }

    Heap(const Heap& that) : cap(that.cap), len(that.len) {
        data = new T[cap];
        memcpy(data, that.data, sizeof(T) * cap);
    }

    ~Heap() { delete[] data; }

    void push(const T &x) {
        data[++len] = x;
        swim(len);
    }

    T pop() {
        swap(data[1], data[len--]);
        sink(1);
        return data[len + 1];
    }

    T top() {
        return data[1];
    }

    bool less(int a, int b) {
        if (a > len || b > len) return false;
        return data[a] < data[b];
    }

    void swim(int idx) {
        int _idx;
        while (idx > 1 && less(idx, _idx = idx / 2)) {
            swap(data[idx], data[_idx]);
            idx = _idx;
        }
    }

    void sink(int idx) {
        int _idx;
        while ((_idx = 2 * idx) <= len) {
            if (_idx < len && less(_idx + 1, _idx)) _idx++;
            if (less(idx, _idx)) break;
            swap(data[idx], data[_idx]);
            idx = _idx;
        }
    }

    bool empty() {
        return len == 0;
    }

    void debug() {
        for (int i = 1; i <= len; i++) cerr << data[i] << " ";
        cerr << endl;
    }
};

int main() {
    Heap<int> heap(65536);
    int N, op1, op2;
    cin >> N;
    char cmd[200];
    for (int i = 0; i < N; i++) {
        cin >> cmd;
        if (strcmp(cmd, "insert") == 0) {
            cin >> op1;
            heap.push(op1);
        }
        else if (strcmp(cmd, "delete") == 0) {
            heap.pop();
        }
        else if (strcmp(cmd, "min") == 0) {
            cout << heap.top() << endl;
        }
    }
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int n,heap[30000],len,x;
char cmd[20];
void minheapify(int x){
    int smallest=x,l,r,tmp;
    while (true) {
        l=x<<1;
        r=l+1;
        if (l <= len && heap[l] < heap[x]) smallest = l;
        if (r <= len && heap[r] < heap[smallest]) smallest = r;
        if (smallest != x) {
            tmp = heap[smallest];
            heap[smallest] = heap[x];
            heap[x] = tmp;
            x = smallest;
        }
        else break;
    }
}
void insert(int x){
    int i=++len,tmp;
    heap[len]=x;
    while (i>1 && heap[i/2]>heap[i])
    {
        tmp=heap[i/2];
        heap[i/2]=heap[i];
        heap[i]=tmp;
        i=i/2;
    }
}
int pop(){
    int ret=heap[1];
    heap[1]=heap[len--];
    minheapify(1);
    return ret;
}
int main() {
    cin>>n;
    len=0;
    for (int i=0;i<n;++i){
        cin>>cmd;
        if (strcmp(cmd,"insert")==0){
            cin>>x;
            insert(x);
        }
        if (strcmp(cmd,"delete")==0) pop();
        if (strcmp(cmd,"min")==0) cout<<heap[1]<<endl;
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <queue>
#include <functional>
using namespace std;

int main() {

    priority_queue<int, vector<int>, greater<int> > que;
    int M; cin >> M;
    while (M--) {
        char op[20];
        cin >> op;
        switch (op[0]) {
        case 'i':
            int tmp; cin >> tmp; que.push(tmp); break;
        case 'd':
            que.pop(); break;
        case 'm':
            cout << que.top() << endl; break;
        }
    }

    return 0;
}

Zsi-r's solution

#include <iostream>
#include <cstring>

using namespace std;

class myqueue
{
    private:
        struct node
        {
            int data;
            node *next;

            node(int x, node *N=NULL){
                data = x; next = N;
            }
            node ():next(NULL){};
            ~node(){};
        };

        node *front,*rear;

        node * move(int i) const;

    public:
        myqueue();
        ~myqueue() ;
        void enqueue(int x);
        int dequeue();
        int getHead()const;
        void sort(int x);
        void traverse()const ;
};

myqueue::myqueue()
{
    front = rear = NULL;
}

myqueue::~myqueue()
{
    node *tmp;
    while(front != NULL)
    {
        tmp = front;
        front = front ->next;
        delete tmp;
    }
}

int myqueue::getHead() const
{
    return front->data;
}

int myqueue::dequeue()
{
    node *tmp=front;
    int value = front->data;
    front= front->next;
    if(front==NULL)rear=NULL;
    delete tmp;
    return value;
}

void myqueue::sort(int x)
{
    if (rear ==NULL)front = rear = new node (x);
    else
    {
        node *p=front,*q=NULL,*tmp;
        while(p!=NULL&&(p->data<x))//p==NULL时,若不分类讨论，p->data会报错，且p!=NULL要放在前面
        {
            q=p;
            p=p->next;
        }
        if (q==NULL)//即应插在队头
        {
            front = tmp = new node(x,p);
        }
        else if (p==NULL)//即应插在队尾
        {
            rear=tmp=new node(x);
            q->next = tmp;
        }
        else {//插在中间
          tmp = new node(x, p);
          q->next = tmp;
        }
    }
}

void myqueue::enqueue(int x)
{
    if (rear ==NULL)front = rear = new node (x);
    else
        rear=rear->next=new node (x);
}

void myqueue::traverse()const
{
    node *p = front;
    while(p!=NULL)
    {
        cout << p->data<<endl;
        p=p->next;
    }
}

int main()
{
    int M;
    int NUM;
    char movement[10];
    myqueue intqueue;
    myqueue output;

    cin >> M;
    for (int i=0;i<M;++i)
    {
        cin >> movement;
        switch(movement[0]){
            case 'i':
                    cin >> NUM;
                    intqueue.sort(NUM);
                    break;
            case 'd':
                    intqueue.dequeue() ;
                    break;
            case 'm':
                    output.enqueue(intqueue.getHead()) ;
                    break;
        }
    }

    output.traverse();

    return 0;
}