[자료구조] [python] [heapq] QHEAP1

 

우선순위 큐(priority queue)는 각 항목에 우선순위가 있는 스텍/큐이다. 파이썬의 heapq 모듈에는 이를 구현 할 수 있는 힙heap 자료형이 있다. 힙(Heaps)는 이진트리이며, 부모노드가 자식노드보다 값이 작거나 같다. 루트인 heap[0]가 heap의 모든 요소들의 최소값이다. 배열, 리스트에서 가장 작은/큰 요소에 반복적으로 접근하는 작업에 유용하다.

 

 

heapq.heapify(list) : 리스트를 힙으로 변환하는 시간 복잡도 O(n)

heapq.heappop(list) : 가장 작은/큰 값 호출시 처리하는 시간 복잡도 O(1)

heapq.heappush(list, item) : 값 조회, 새로운 값 추가, 수정시 처리하는 시간 복잡도는 O(log n)

heapq.heappushpop(list, item) : 힙에 새 항목을 추가한 후, 가장 작은 항목을 제거한 후 반환한다 

heapq.heapreplace(list, item) : 힙의 가장 작은 항목을 제거하고 반환한 후, 새 항목을 추가한다 

 

다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다.  

Hackerrank의 Data structures 관한 문제 중에서 Easy에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/challenges/qheap1/problem

QHEAP1 | HackerRank

 

 

* heapq에는 항목을 찾아서 지우는 함수는 없다. 만약, 앞에서부터 순회하며 항목을 지우는 경우, 다시 이진 트리가 재구성되므로, O(log n)의 시간이 걸리게 된다. 힙큐가 된 리스트를 앞에서부터 순회하여 특정 항목을 찾아서, 삭제했을 경우(list.remove(A), A항목을 찾아서 지움) heapq.heapify(list)를 통해서 다시 이진트리 형태로 만들어줘야 한다. 따라서, 특정 항목을 삭제하고자 할 경우, 삭제하는 정보를 담은 별로의 자료형을 만들거나, 힙 자료형에 삭제/보존 하는 정보를 담은 형태로 값을 저장하는 것이 좋다. 

 

import heapq
V = []
isin = set()

for _ in range(int(input())):
    command = list(map(int, input().split()))
    
    if command[0] == 1:
        heapq.heappush(V, command[1])
        isin.add(command[1])
    elif command[0] == 2:
        isin.discard(command[1])
    elif command[0] == 3:
        
        while V[0] not in isin:
            heapq.heappop(V)
            
        print(V[0])