AcWing 839. 模拟堆
原题链接
简单
作者:
gzh668899
,
2022-12-12 23:06:52
,
所有人可见
,
阅读 131
#include <iostream>
using namespace std;
const int N = 100000;
typedef struct heap
{
int buf[N];
int size;
}HEAP;
HEAP minHeap;
void heapinit(HEAP *heap)
{
heap->size = 0;
}
void heapswap(HEAP *heap, int idx1, int idx2)
{
int temp = heap->buf[idx1];
heap->buf[idx1] = heap->buf[idx2];
heap->buf[idx2] = temp;
}
void up(HEAP *heap, int cidx)
{
for (int pidx = (cidx - 1) / 2; cidx > 0; pidx = (cidx - 1) / 2)
{
if (heap->buf[cidx] > heap->buf[pidx])
break;
heapswap(heap, cidx, pidx);
cidx = pidx;
}
}
void down(HEAP *heap, int pidx)
{
for (int cidx = pidx * 2 + 1; cidx < heap->size; cidx = pidx * 2 + 1)
{
if (cidx + 1 < heap->size && heap->buf[cidx + 1] < heap->buf[cidx])
cidx++;
if (heap->buf[cidx] > heap->buf[pidx])
break;
heapswap(heap, cidx, pidx);
pidx = cidx;
}
}
void heapPush(HEAP *heap, int x)
{
heap->buf[heap->size] = x;
heap->size++;
}
int heapPop(HEAP *heap)
{
heapswap(heap, 0, heap->size-1);
heap->size--;
down(heap, 0);
return heap->buf[heap->size];
}
int main()
{
int m;
cin >> m;
while (m--)
{
string op;
int x;
cin >> op;
if (op == "I")
{
cin >> x;
heapPush(&minHeap, x);
} else if (op == "DM") {
heapPop(&minHeap);
} else if (op == "PM") {
cout << minHeap.buf[0];
}
}
}