백준알고리즘 1927번, 최소 힙 풀이

자연수 x를 입력받아 최소 힙에 입력하고 출력하는 문제입니다.

힙을 구현할때 push같은 경우에는 빈 정점에 넣어주기만해서 금방 잤는데

pop같은 경우에는 마지막 정점을 루트로 옮기고 루트와 자식노드간에 비교를 한번만 해서 계속 답이 틀렸었네요. 위치를 옮기고 나면 옮긴 위치에서 또 비교를 계속 해줘야됩니다. DFS나 BFS로 구현하면되는데, 저는 큐를 활용해 BFS로 구현했습니다

--------------------------------------------------------------------------------------------

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <functional>

#include <utility>

using namespace std;

class Heap_min {

private:

unsigned int vertex[100000];

int empty_vertex;

int size;

queue<int> q;

public:

Heap_min() {

memset(vertex, 0xff, sizeof vertex);

empty_vertex = 0;

size = 0;

}

void push(unsigned int x) {

int parent,curr,temp;

size++;

vertex[empty_vertex] = x;

curr = empty_vertex;

parent = (curr - 1) / 2;

empty_vertex++;

while (vertex[parent] > vertex[curr]) {

temp = vertex[parent];

vertex[parent] = vertex[curr];

vertex[curr] = temp;

curr = parent;

parent = (curr - 1) / 2;

}

}

unsigned int pop() {

int lchild, rchild, parent, temp;

unsigned ret;

if (size == 0)

return 0;

size--;

ret = vertex[0];

vertex[0] = vertex[--empty_vertex];

vertex[empty_vertex] = 0xffffffff;

parent = 0;

q.push(parent);

while(!q.empty()){

if (q.front() > 49999) {

q.pop();

continue;

}

parent = q.front();

lchild = parent * 2 + 1;

rchild = parent * 2 + 2;

q.pop();

if(vertex[parent] > vertex[lchild]){

temp = vertex[parent];

vertex[parent] = vertex[lchild];

vertex[lchild] = temp;

q.push(lchild);

}

if (vertex[parent] > vertex[rchild]) {

temp = vertex[parent];

vertex[parent] = vertex[rchild];

vertex[rchild] = temp;

q.push(rchild);

}

}

return ret;

}

};

int main(void) {

Heap_min hm;

int N;

unsigned int x;

#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

scanf("%d", &N);

for (int i = 0; i < N; i++) {

scanf("%d", &x);

if (x == 0) {

printf("%d\n", hm.pop());

}

else {

hm.push(x);

}

}

#ifndef ONLINE_JUDGE

fclose(stdin);

fclose(stdout);

#endif

return 0;

}