# 11215: 【原1215】bernoulli

### 题目描述

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

## Description

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

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

3.min，输出最小值

## Sample Input1

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

## Sample Output1

``````6
3
``````

## 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();
};

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>
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()) {
}
}
}

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();
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;
}
}

{
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':