[힙(Heap)] 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

 

 

heapqueue 알고리즘

  - https://docs.python.org/ko/3/library/heapq.html

 

heapq.heapify(x)

리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

 

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

iterable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환합니다. key가 제공되면 iterable의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정합니다 (예를 들어, key=str.lower). 다음과 동등합니다 == sorted(iterable, key=key, reverse=True)[:n]

 

 

 

- 코드

import heapq
def solution(operations):
    queue = []
    heapq.heapify(queue)
    for i in operations:
        temp = i.split(' ')
        op = temp[0]
        operand = int(temp[1])
        if op=='I':
            heapq.heappush(queue, operand)
        elif len(queue) > 0 and op=='D' and operand >= 0:
            queue = heapq.nlargest(len(queue), queue)[1:]
            heapq.heapify(queue)
        elif len(queue) > 0:
            heapq.heappop(queue)
    if len(queue) == 0:
        return [0, 0]
    queue = sorted(queue)
    return [queue[-1], queue[0]]