최대 힙 - 11279

1. 개요

문제 링크: https://www.acmicpc.net/problem/11279

2. 코드

import sys

def swap(a, b):
    global heap
    temp = heap[a]
    heap[a] = heap[b]
    heap[b] = temp

def upHeapify(idx):
    global heap, size
    parent = idx // 2
    while parent >= 1:
        if heap[parent] > heap[idx]:
            return
        swap(parent, idx)
        idx = parent
        parent = parent // 2

def downHeapify(idx):
    global heap, size
    left = idx * 2
    while left <= size:
        right = left + 1
        if right <= size:
           if heap[left] < heap[right]:
               left = right
        if heap[left] < heap[idx]:
            return
        swap(left, idx)
        idx = left
        left = left * 2

def pop():
    global size, heap
    root = heap[1]
    heap[1] = heap[size]
    size -= 1
    downHeapify(1)
    heap.pop()
    return root

def addNode(data):
    global size, heap
    heap.append(data)
    size += 1
    upHeapify(size)

size = 0
n = int(input())
heap = [0]
for i in range(0, n):
    x = int(sys.stdin.readline().rstrip())
    if x == 0:
        if size == 0:
            print('0')
        else:
            print(pop())
    else:
        addNode(x)

3. 풀이 메모

1. upHeapify 알고리즘

1. 입력 받은 idx의 parent를 설정한다.
2. 입력 받은 idx와 parent를 비교하면서, '최대힙' 형태가 갖춰졌는지 확인한다.

• 만약 갖춰지지 않았다면, 두 노드 값을 스왑하고 idx와 parent를 상위로 갱신한다.

3. 이상의 과정을 parent가 root 노드가 될 때까지 반복한다. 그 이상은 루프를 탈출한다.

2. downHeapify 알고리즘

1. 입력 받은 idx의 왼쪽 자식 노드 left를 설정한다.
2. left가 전체 힙 size의 이하를 만족한다면 2부터 다음을 반복한다.
3. idx의 오른쪽 자식 노드 right를 left+1로 설정한다.
4. 만약 right가 size보다 작고, heap[left] < heap[right]라면, left를 right로 갱신한다.
5. 만약 heap[left] < heap[idx]가 만족된다면, 함수를 탈출한다.
6. 두 노드 left와 idx를 스왑한다.
7. 두 노드 left와 idx를 한 단계 아래의 값으로 갱신한다.
8. 3번으로 돌아가 다시 이상의 과정을 반복한다.

3. addNode 알고리즘

1. heap의 가장 끝에 입력 받은 data를 추가한다.
2. size를 1 증가시킨다
3. upHeapify(size)를 호출한다.

4. pop 알고리즘

1. heap[1]을 root 변수에 저장한다.
2. heap[1]을 heap의 가장 끝 저장값 heap[size]로 설정한다.
3. size를 1 감소시킨다.
4. downHeapify(1)을 호출한다.
5. heap의 가장 마지막 원소를 직접 제거한다.
6. root를 리턴시킨다.

4. 코멘트

자료구조인 최대 힙(Max heap)을 직접 구현하는 문제이다. 학부때 배우긴 했지만 군대와 함께 기억의 저편으로 건너간 상태라서 오랜만에 복습할 기회가 될 수 있었다.