Python | 힙(Heap)

힙 알고리즘(heapq)

힙은 트리형식으로 구성되나 보통은 최소값이 맨 위로 올라가는 최소 힙으로 구현되어 있어서 가장 작은 값을 효율적으로 관리 가능합니다. 그래서 최소값을 찾고 pop하기는 쉽습니다. 반면 최대값은 검색이 가능하지만 pop하기는 어려운 구조이기에 아래 문제를 풀 때는 리스트로 변경해서 remove하고 다시 heapify로 힙 구조로 변환하였습니다.

 

# 프로그래머스 | 이중우선순위큐

from heapq import heappush, heappop, heapify

def solution(operations):
    heap = []
    for op in operations:
        if op[0] == "I":
            heappush(heap, int(op[2:]))
        elif op == "D -1" and heap:
            heappop(heap)
        elif op == "D 1" and heap:
            heap = list(heap)
            heap.remove(max(heap))
            heapify(heap)
                     
    if not heap:
        return [0, 0]
    return [max(heap), min(heap)]