[백준] 11279 최대 힙 풀이

힙은 쉬우면서 어려운 자료구조이다. 개념은 매우 쉬운데 구현에 있어서 놓치기 쉬운 부분들이 있기 때문이다.

문제 자체는 단순한 힙의 구현이다. 

힙에 저장하는 부분이다. 저장할 때에는 위에 있는 노드와 비교를 진행한다. 

public static void push(int n) {

heap[++index] = n;

// 정렬

for (int i = index; i > 1; i /= 2) {

if (heap[i] > heap[i/2]) {

int temp = heap[i]; heap[i] = heap[i/2]; heap[i/2] = temp;

} else {

break;

}

}

}

여기서 중요한 것은 인덱스의 범위이다. for 문안의 조건을 잘 생각해야 한다. 

두 번째로 조금 까다로운 값 꺼내기 작업이다.

public static int pop() {

int max = heap[1];

heap[1] = heap[index];

heap[index--] = 0;

for (int i = 1; i*2 <= index; ) {

if (heap[i] > heap[i*2] && heap[i] > heap[i*2+1]) {

break;

} else if (heap[i*2] > heap[i*2+1]) {

int temp = heap[i]; heap[i] = heap[i*2]; heap[i*2] = temp;

i = i*2;

} else {

int temp = heap[i]; heap[i] = heap[i*2+1]; heap[i*2+1] = temp;

i = i*2 + 1;

}

}

return max;

}

역시 마찬가지로 for문안의 조건들을 잘 보아야 한다. i가 증가하는 조건은 자식 노드 2개와 비교할때마다 달라진다. 왼쪽 자식노드로 교환을 하면 2를 곱하고 오른쪽 자식노드와 교환을 하면 2를 곱하고 1을 더해주어야 인덱스가 맞기 때문이다.