[파이썬] 프로그래머스 - 이중우선순위큐

---

📌  Heap

Heap은 데이터를 정렬된 상태로 저장하기 위해서 사용하는 자료구조이다.

파이썬의 heapq 모듈은 이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다.

min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은 값은 언제나 인덱스 0, 즉, 이진트리의 루트에 위치한다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.

 

 

 

이 문제에서 힙의 최댓값을 제거하는데 약간의 요령이 필요한데 바로 nlargest라는 함수이다.

heapq 모듈에 이 용도에 적합한 nlargest()와 nsmallest() 함수가 있다.

• heapq.nlargest(n, iterable, key=None)
• heapq.nsmallest(n, iterable, key=None)

print(heapq.nlargest(3, nums)) #-> [99, 8, 4]

print(heapq.nsmallest(3, nums)) #-> [-5, -4, 0]

 

이 때 heap = heapq.nlargest(len(heap), heap)[1:] 을 통해서 heap을 내림차순으로 가져오고 이 중 가장 첫번째 즉 가장 큰 수를 제거하고 다시 heapify 시키면 힙의 최대값이 제거된 결과가 된다.

EX) heap = heapq.nlargest(len(heap), heap)[1:] 을 통해 [1, 3, 5, 4, 8, 7] -> [8, 7, 5, 4, 3, 1] ->[7, 5, 4, 3, 1] : 결과적으로 최대값 제거

 

 

코드

import heapq

def solution(operations):
    heap = []
    answer = []
    for operation in operations:
        if operation.startswith('I'):
            heapq.heappush(heap, int(operation.split()[1]))
        elif len(heap) == 0:
            continue
        else:
            if (operation.split()[0] == 'D') and (operation.split()[1] == '1'):
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)
            elif (operation.split()[0] == 'D') and (operation.split()[1] == '-1'):
                heapq.heappop(heap)
    if len(heap) == 0:
        return [0, 0]
    else:
        return [heapq.nlargest(1, heap)[0], heap[0]]