[자료구조] heap(힙), priority queue(우선순위 큐)

1. priority queue란? 

 

우선순위 큐에서는 우선순위가 가장 높은, (또는 낮은) 원소를 먼저 삭제한다고 하고, 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다고 합니다.  FIFO인 일반 큐와는, 우선순위 순서로 pop하는 기능이 다릅니다. 

 

우선순위 큐가 왜 필요하냐면, 똑같은 기계를 쓰는 소비자 중에 3000원을 낼 사람, 1000원을 낼 사람, 2000원을 낼 사람이 있다고 하면 기계는 3000원을 낼 사람을 먼저 쓰게 해주고, 그 다음 2000원, 그 다음 1000원을 낼 사람 순으로 써주게 하는 것이 가게 주인 입장에서 최고이죠? 이런식으로 큐에 넣는 원소들에 우선순위를 부과해야 할 때, 우선순위 큐를 쓰면 됩니다. 이 경우는 max priority queue이고, 반대 경우에는 min priority queue를 쓰면 됩니다. 

 

 

maxPriorityQueue의 ADT는 다음과 같습니다.

• create
• isEmpty
• top : 가장 큰 원소를 리턴해준다
• pop : 가장 큰 원소를 리턴하고, 힙에서 지운다.
• push

 

priority queue를 표현하는 가장 간단한 방법은 '무순서 선형 리스트(list)'로 표현하는거라고 한다. isEmpty는 O(1), top은 O(n), push 는 O(1)시간이 걸린다고 한다. pop은 O(n)이다. 하지만 array나 linked list를 사용했을 때 보다, heap을 사용했을 때 훨씬 시간이 단축되기 때문에 heap을 사용합니다. 최대 heap가 사용될 떄는 isEmpty랑 top은 O(1), push와 pop은 O(logn)이라고 합니다. 

 

 

그렇다면 heap은 무엇일까요?

 

'힙'이라는 자료구조를 많이 들어봤는데, 설명할 수 있을정도로는 알지 못해서 이번 기회에 정리해보려고 합니다!

힙의 목적은 'priority queue(우선순위 큐)'의 구현이라고 합니다.

 

2. heap이란?

 

영어로는 '더미'라는 뜻이다!

 

[Heap]

max tree는, 각 노드의 키 값이 (자식이 있다면) 그 자식의 키값보다 작지 않은 트리이다.

max heap는 max tree이면서 complete binary tree이다. 

 

쉽게 정의하면, heap이란

1) complete binary tree이다. 

2) 부모값 ≧ 자식 값

 

complete binary tree는 이런것이다. 

https://sweetdev.tistory.com/113

 

얘는 max tree의 조건을 만족한다.

 

얘는 max heap의 조건을 만족한다. complete binary tree의 형태도 만족하니까!!

 

 

heap에 저장할 때 

제일 아래에 넣고, 부모와 크기를 비교해서 부모보다 크면 swap한다. 

 

heap에 삭제할 때

루트값을 지운다. 그리고 그 자리에 자식중 큰 값을 올려준다. 

 

heap의 구현은 주로 array를 이용해서 한다. 

 

3. 중간값 (median) 구하기?

이진 검색 트리로 풀어도 되지만 구현이 복잡하다...

 

[힙으로 풀기]

숫자들을 정렬

앞의 절반을 최대 힙, 뒤의 절반을 최소 힙에 넣음

수열 길이가 홀수라면 최대 힙에 하나 더 넣음

그러면 다음을 만족

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다
2. 최대 힙의 최대 원소는 최소 힙의 회소 원소보다 작거나 같다

그러면 이 수열의 중간 값은 최대 힙의 루트에 있음

삽입

1. 둘 중 한 힙에 숫자 추가해 1번 식 만족
2. 2번 식이 만족되지 않으면, 최대 힙의 최대 원소와 최소 힙의 최소 원소 맞바꿈

숫자를 하나만 추가했으므로 한 번만 숫자들을 바꿔도 2번 불변식 유지 가능

 

 

 

파이썬으로 구현하기

 

heapq 모듈을 이용해서 구현한다. 

 

# 1655번 가운데를 말해요
import sys
import heapq

N = int(sys.stdin.readline())
list = []

max_heap = []
min_heap = []

for i in range(N):
    num = int(sys.stdin.readline())

    if len(max_heap) == len(min_heap):
        # max 에다가 붙이기
        heapq.heappush(max_heap, (-num, num))
    else:
        # min 에다가 붙이기
        heapq.heappush(min_heap, num)

    if len(max_heap) > 0 and len(min_heap) > 0:
        if max_heap[0][1] > min_heap[0]:
            # swap해주기
            fromMax = heapq.heappop(max_heap)
            fromMin = heapq.heappop(min_heap)

            heapq.heappush(max_heap, (-fromMin, fromMin))
            heapq.heappush(min_heap, fromMax[1])

    print(max_heap[0][1])

 

 

[참고 자료]

https://velog.io/@ember/23.-우선순위-큐와-힙

https://chanhuiseok.github.io/posts/ds-4/

https://sweetdev.tistory.com/852