파이썬 백준 11279 최대 힙

import sys   input = sys.stdin.readline heap = [''] n = int(input()) for i in range(n) :     e = int(input())     if e == 0 :         if heap == [''] :             print(0)         else :             e = heap[-1]             heap[1], heap[-1] = heap[-1], heap[1]             print(heap[-1])             del heap[-1]             index = 1             while index * 2 < len(heap) :                 a = index * 2                 if len(heap) == index * 2 + 1 :                     next = a                 else :                     b = a + 1                     if heap[a] >= heap[b] :                         next = a                     else :                         next = b                 if e < heap[next] :                     heap[index], heap[next] = heap[next], heap[index]                     index = next                 else :                     break     else :         heap.append(e)         index = len(heap) - 1         while index > 1 :             if e > heap[index//2] :                 heap[index], heap[index//2] = heap[index//2], heap[index]                 index = index // 2             else :                 break

1주차에 힙 정렬을 구현할 때 썼던 힙을 직접 구현하는 문제이다.

힙에서 i번째 원소의 부모는 i//2번째이고, 자식은 2i, 2i+1번째이다.

이를 이용해 부자간에만 원소의 변경이 이루어지고, 입출입은 [-1]에서만 일어나 del에 의한 재정렬을 피한다.

 

새로 입력받은 원소는 먼저 [-1]에 저장된다.

그후 i//2번째와의 교환을 반복하여 부모가 자신보다 클 때 안착한다.

최댓값 [0]을 출력할 땐 먼저 [-1]과 자리를 바꾼 뒤 del한다.

머리에 올라간 막내는 2i, 2i+1중 큰 것과의 비교로 자기에게 맞는 자리까지 내려간다.

 

heapq라는 것을 import하면 이 긴 코드를 안짜고도 heap을 쓸 수 있다고 한다.

최소힙만 제공하지만, 원소를 입출력할 때 부호를 뒤집으면 최대힙의 기능을 하게 된다.