#16 우선순위 큐(Priority Queue)

 대기열(Queue)은 본래 먼저 삽입된 데이터가 먼저 나가는 FIFO 자료구조이다.  하지만 경우에 따라서 나중에 들어왔더라도 먼저 처리해야하는 데이터가 존재할 수도 있다.  이러한 경우에는 들어온 순서와는 관계없이 우선순위가 높은 것을 먼저 내보내는 우선순위 큐를 사용한다.  물론 매번 데이터를 삽입할 때 마다 우선순위 기준으로 정렬을 실행하는 비효율적인 방식을 사용할 수는 없으니 우선순위 큐에는 힙(heap)이 사용된다. 우선순위 큐와 힙은 그 기능이 완전히 동일하다고 봐도 좋다. 

 

1. 힙(Heap) 의 원리

 힙(heap)은 완전 이진트리형태의 자료구조이다.  삽입, 삭제시에 항상 느슨한 정렬상태, 즉 부모노드가 자식노드보다 항상 크거나(최대 힙) 항상 작은(최소 힙) 상태를 유지하도록 하여 언제든지 루트노드를 참조하면 들어있는 데이터중 최소/최대 값을 바로 알아낼 수 있다.  

 

힙의 구현은 주로 배열을 사용하여 이뤄진다.  트리라곤 해도 완전 이진트리 형태이기에 그쪽이 훨씬 구현이 쉽기 때문이다.  힙의 삽입, 삭제 절차와 이에따라 힙을 구현한 코드는 다음과 같다.  여기서는 최대힙을 기준으로 설명한다.

 

* 삽입

 ① 힙으로 쓸 배열의 맨 끝에 원소를 삽입한다.

 ② 삽입된 위치에서부터 부모노드를 탐색하여 부모노드가 존재하고 자신보다 값이 작다면 서로 위치를 바꾼다.

 ③ ② 과정을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.

 

* 삭제

 ① 반환할 힙의 최댓값(루트노드 값)을 별도의 변수에 저장해둔다.

 ② 루트노드의 값에 힙의 맨 끝의 값을 덮어씌우고 맨 끝의 값은 제거한다.

 ③ 루트노드에서부터 자식노드를 탐색하여 자신보다 더 큰 자식노드가 있다면 서로 위치를 바꾼다.

     두 자식노드 모두 자신보다 크다면 둘 중 더 큰 쪽과 위치를 바꾼다.

 ④ ③ 과정을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.

 ⑤ 미리 저장해둔 힙의 최댓값을 반환한다. 

def heappush(h, e):
    # 삽입할 원소를 힙의 맨 끝에 삽입
    h.append(e)
    
    # 삽입된 원소의 현재위치
    i = len(h) - 1
    
    # 삽입된 원소의 부모노드 
    p = i // 2 - 1 + i % 2
    
    # 삽입한 원소가 루트노드가 아닐 동안 반복
    while i > 0:
    	# 부모 노드
    	p = i // 2 - 1 + i % 2
        
    	# 만약 부모노드의 값이 삽입된 원소보다 작다면 삽입된 노드와 자리를 바꾼다
        # 계속해서 탐색하기 위해 삽입된 원소의 현재위치를 부모노드의 위치로 갱신
        if h[p] < h[i]:
            h[p], h[i] = h[i], h[p]
            i = p
            
        # 부모노드의 값이 삽입된 원소보다 크다면 더이상 탐색할 필요가 없음
        else:
            break


def heappop(h):
    # 비어있는 힙에서 값을 얻으려한다면 None 반환
    if not h:
        return None

    # 힙에 원소가 하나뿐이라면 pop한 결과 반환
    if len(h) == 1:
        return h.pop()

    # 반환할 루트노드 값을 저장
    res = h[0]
    
    # 힙의 마지막 값을 pop하여 루트노드에 저장
    h[0] = h.pop()
    
    # 현재 노드
    i = 0
    while True:
    	# 좌, 우 자식 노드
    	l, r = i * 2 + 1, i * 2 + 2
        
    	# 값을 바꿀 타겟 노드를 현재 노드로 설정
        t = i
        
        # 좌측 자식 노드가 존재하고 그 값이 타겟 노드의 값 보다 크다면
        # 좌측 자식 노드를 타겟 노드로 설정
        if l < len(h) and h[l] > h[t]:
            t = l
            
        # 우측 자식 노드가 존재하고 그 값이 타겟 노드의 값 보다 크다면
        # 우측 자식 노드를 타겟 노드로 설정
        if r < len(h) and h[r] > h[t]:
            t = r
            
        # 타겟 노드를 찾았다면 현재 노드와 서로 값을 바꾼다
        # 현재 노드를 타겟 노드로 갱신하고 좌우 자식노드를 
        if t != i:
            h[i], h[t] = h[t], h[i]
            i = t
        # 타겟 노드를 찾지 못했다면 더이상 탐색할 필요가 없음
        else:
            break
            
    # 미리 저장해둔 루트 노드 값 반환
    return res

 배열(리스트)를 인자로 받아 힙을 유지하도록 삽입/삭제하는 함수를 구현하는 방식으로 힙을 구현하였다.  힙의 삽입/삭제 연산은 O(logN)의 시간복잡도를 가지기에 삽입에 시간이 조금더 걸리긴 하지만 최댓값, 최솟값을 자주 구해야하는 경우 단순 배열에 삽입한 뒤 선형탐색을 하는 것 보다 훨씬 효율적이다.  삽입/삭제의 과정을 조금만 수정하면 최소힙, 절댓값 힙도 구현 가능하다. 

 

2. heapq 모듈

 힙의 구현이 그리 어려운 것은 아니지만 시간이 제한된 코딩테스트에서 힙을 직접 구현해가며 쓰는것은 시간낭비일 수 있다. python에서는 heapq 모듈을 제공하고 있어 굳이 직접 구현할 필요 없이 힙 삽입, 삭제, 변환 연산을 사용할 수 있다. 

 

* heapq.heappush(h, e)

 리스트 h에 힙 구조를 유지하도록 e를 삽입한다. 

 

* heapq.heappop(h)

 리스트 h에서 힙 구조를 유지하도록 최솟값을 제거하고 제거된 값을 반환한다.

 

* heapq.heapify(h)

 리스트 h를 힙 구조로 변환한다.

 

python의 heaqp 모듈은 기본적으로 최소 힙으로 구현되어있다.  최대 힙으로 사용할 경우 넣으려는 값에 음수를 취해주고 꺼낼 때도 마찬가지로 음수를 취하는 방식을 사용해야한다.

 

heapq 모듈을 사용하여 우선순위 큐 관련 문제(https://www.acmicpc.net/problem/1655)를 해결하는 절차와 이를 구현한 코드는 다음과 같다.

 

① 최소 힙 minq, 최대 힙 maxq를 각각 생성한다.

② 수열을 순회하며 각 수가 최소 힙의 최솟값 이상이라면 최소힙에, 그렇지 않다면 최대힙에 그 수를 삽입한다.

③ 최대 힙과 최소 힙의 크기차이가 1을 넘지 않도록 유지한다

④ 두 힙의 크기가 같다면 최대힙의 루트노드 값이, 다르다면 큰 쪽의 힙의 루트노드 값이 현 시점의 중간값이 된다.

import sys
from heapq import heappush, heappop


def sol1655():
    maxq, minq = [], []
    n, *nums = map(int, sys.stdin.read().split())
    answer = []
    for num in nums:
    	# 최대 힙이 비어있거나 수가 최대 힙의 최댓값 이상이라면 최대힙에 heappush
        if not maxq or num <= -maxq[0]:
            heappush(maxq, -num)
        # 그렇지 않다면 최소 힙에 heappush
        else:
            heappush(minq, num)
            
        diff = len(maxq) - len(minq)
        # 두 힙의 크기차이가 1보다 커지면 균형을 맞추고 크기차이를 0으로 세팅
        # maxq가 minq보다 2 크다면 maxq에서 원소 하나를 제거하여 minq에 넣어준다
        if diff == 2:
            heappush(minq, -heappop(maxq))
            diff = 0
        # minq가 maxq보다 2 크다면 minq에서 원소 하나를 제거하여 maxq에 넣어준다
        elif diff == -2:
            heappush(maxq, -heappop(minq))
            diff = 0

	# 두 힙의 크기차이가 없거나 maxq쪽이 크면 maxq의 최댓값이 중간값
        # 그렇지 않다면 minq의 최솟값이 중간값
        answer.append(-maxq[0] if diff >= 0 else minq[0])

    return '\n'.join(map(str, answer))

최대 힙의 최댓값이 최소 힙의 최솟값보다 항상 작으며 최대 힙과 최소 힙의 크기 차이가 1을 넘지않는다는 규칙을 유지하면서 수를 삽입할 경우 항상 두 힙의 길이가 같거나 최대힙이 크다면 최대힙의 최댓값이, 그렇지 않다면 최소힙의 최솟값이 그 시점의 중간값이 된다.