[백준_11279] 우선순위 큐, 최대 힙

[백준_11279] 우선순위 큐, 최대 힙

최대 힙을 이용해 원하는 값을 출력하는 우선순위 큐 문제를 풀어보았다.

내 코드 - 모듈 없이

do it! 책대로 풀었는데 시간초과가 떳다.... 남들은 더 간단하게 했는지 input()만 sys.stdin.readline()으로 고쳐주면 통과 된다는데 이 방식으론 통과가 안된다. 그래서 옆에 친구한테 물어보니 모듈을 쓰면 된단다 =.=;; 그래도 원리 이해한 거에 의의를 두는 걸로

import sys

def heap_sort(a):

    def down_heap(arr, left, right): # left : 기준, right가 n-1 가장 마지막 leaf
        
        tmp = arr[left]
        parent = left #left 뺴고 다 heap 구조 가정

        while parent < (right + 1) // 2:
            cl = 2 * parent + 1
            cr = cl + 1
            child = cr if cr <= right and arr[cr] > arr[cl] else cl
            # child = cl if arr[cl] > arr[cr] and cr <= right else cr
            if tmp >= arr[child]:
                break
            arr[parent] = arr[child]
            parent = child
        arr[parent] = tmp

    n = len(a)

    for i in range((n-1)//2, -1, -1): # a[i] ~ a[n-1]을 힙 만들기
        down_heap(a, i, n-1)

    for i in range(n-1, 0, -1): # 배열 바꾸기
        a[0], a[i] = a[i], a[0]
        down_heap(a, 0, i-1)

a = []
n = int(sys.stdin.readline())
for _ in range(n):
    var = int(sys.stdin.readline())
    if var == 0:
        if len(a) == 0:
            print(0)
        else:
            heap_sort(a)
            print(a.pop(-1))
    else:
        a.append(var)

 

heap 모듈

heapq 모듈은 이진 트리 기본의 최소 힙(min heap) 자료 구조를 제공한다. 자바에 익숙한 사람이라면 priorityQueue 클래스와 비슷하다고 하니 참고하시길.

min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은 값은 언제나 인덱스 0, 즉 루트에 존재하는 값이다.

 

모듈 import : import heapq

원소 추가 : heapq.heappush(list명, 추가 값)

원소 삭제 : heapq.heappop(list명)) # 가장 작은 수가 삭제 된 후 그 다음 작았던 값이 인덱스 0으로 간다.

최소값 확인 : heapp[0]

기존 리스트 heapify : heapq.heapify(list명)

최대 힙 만들기 : 튜플(tuple)을 이용하여 (-추가 값, 추가 값)을 넣어 준다. 이때 원소 값의 부호가 바뀌어  list[0] 기준 최소힙이고 list[1]기준 최대 힙이기 때문에 list[1]을 출력해주면 된다.

-> max_heap = (heapq.heappush(list명, (-추가 값, 추가 값))

-> max_item = heapq.heappop(max_heap)[1]

 

내 코드 - 모듈 사용

import sys
import heapq
input = sys.stdin.readline

heap = []
n = int(input())
for i in range(n):
    var = int(input())
    if var == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap, (-var, var))