TIL 240315

2930. 힙

본 문제에서는 최대 힙(max heap)을 올바르게 구현하였는지 확인할 수 있다.
초기에 최대 힙이 비어있을 때에 다음의 2가지 연산을 수행하는 프로그램을 작성하자.

python은 heapq라는 최소 힙을 기준으로하는 내장 함수가 있어서 이를 사용하면 해당 문제를 해결할 수 있다. 하지만 힙을 직접 구현해보자는 생각을 해서 직접 구현을 시도해 보았다.

실패 코드

 def heapify(node):
     parent = node // 2
     left = parent * 2
     right = parent * 2 + 1

     if parent == 0:
         return

     if right < len(tree):
         if tree[parent] < tree[left] and tree[parent] < tree[right]:
             if tree[left] <= tree[right]:
                 tree[parent], tree[right] = tree[right], tree[parent]
             else:
                 tree[parent], tree[left] = tree[left], tree[parent]
             heapify(parent)
     else:
         if tree[parent] < tree[node]:
             tree[parent], tree[node] = tree[node], tree[parent]
             heapify(parent)


 T = int(input())
 for test_case in range(1, T + 1):
     n = int(input())
     tree = [0]
     result = []
     for _ in range(n):
         cal = list(map(int, input().split()))
         if cal[0] == 1:
             tree.append(cal[1])
             heapify(len(tree) - 1)
         else:
             if len(tree) > 1:
                 tree[1], tree[-1] = tree[-1], tree[1]
                 result.append(tree.pop())
                 heapify(len(tree) - 1)
             else:
                 result.append(-1)

     print(f"#{test_case} {' '.join(list(map(str, result)))}")

연산 1인 경우 입력받은 노드값을 힙에 넣고 힙 속성이 유지되도록 하고 삭제 연산에서는 root와 마지막 노드 값을 바꾼뒤 마지막 노드를 삭제하고 힙 속성을 유지하도록 코드를 구현해보았지만 샘플 데이터는 정답이 나왔지만 다른 테스트 케이스에서는 실패하였다. 일단 heapq를 사용하여 해당 문제는 pass하였다.

성공 코드

import heapq


T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    tree = []
    result = []
    for _ in range(n):
        cal = list(map(int, input().split()))
        if cal[0] == 1:
            heapq.heappush(tree, -cal[1])
        else:
            if tree:
                result.append(-heapq.heappop(tree))
            else:
                result.append(-1)

    print(f"#{test_case} {' '.join(list(map(str, result)))}")

해당 문제는 최대 힙을 기준으로 하기 때문에 "-"를 사용하여 최대 힙을 구현

---

오늘은 캠프의 일정과 개인 일정까지 있어 자세히 공부하지 못했지만 시간이 날 때 heapq 함수를 열어봐서 내가 구현한 heap 코드와 다른 부분을 찾아 실패한 코드를 활용하여 heapq를 사용하지 않고 pass를 얻을 것이다.