[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) / Python 파이썬

 

자료구조는 우선순위(priority_queue)를 구현하기 위해 사용하는 자료구조 중 하나다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징인데, 표로 나타내면 다음과 같다.

자료구조추출되는 데이터

스택(stack)	가장 나중에 삽입된 데이터
큐(queue)	가장 먼저 삽입된 데이터
우선순위 큐(priority_queue)	가장 우선순위가 높은 데이터

우선순위 큐를 구현할 때는 내부적으로 최소 힙(min_heap) 혹은 최대 힙(max_heap)을 이용한다. 최소 힙을 이용할때는 값이 가장 낮은 데이터가 먼저 삭제되며, 최대 힙은 값이 큰 데이터가 가장 먼저 삭제됨을 알아두자.

파이썬에서 우선순위 큐 라이브러리를 사용할때는 default값이 최소 최소 힙(min_heap)으로 설정되어있는데, 최대 힙(max_heap)으로 사용하고 싶다면, 값에 음수 부호(-)를 붙여서 넣었다가 heapq.heappop 할 때 다시 음수 부호(-)를 붙여 원래의 값으로 돌리면 된다.

# desc heap_example
def heapsort(n):
    h = []
    result = []

    for i in n:
        heapq.heappush(h, -i)

    for i in range(len(h)):
        result.append(-heapq.heappop(h))

    return result

우선순위를 구현방식의 시간복잡도는 다음과 같다.
| 우선순위 큐 구현방식 | 삽입 시간 | 삭제 시간 |
| :----: | :----: | :----: | :----: |
| 리스트(list) | O(1) | O(1) |
| 힙(heap) | O(logN) | O(logN) |

데이터의 개수가 N개 일때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 가정하면 전체 연산 횟수는 대략 2NlogN으로 빅오표기법에 따라서 O(NlogN)이 될 것이다.

 

자료구조 ‘힙(heap)’

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조

 

* 이진탐색트리와 힙의 공통점과 차이점

• 공통점: 힙과 이진 탐색 트리는 모두 이진 트리임
• 차이점:
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
    • 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

 

따라서 해당 타겟(최대 or 최소) 를 만들어주기위해 SWAP 을 반복함.

이미지 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

0. 함수 사용하기

• heapq.heappush(heap, item): item을 heap에 추가
• heapq.heappop(heap): heap에서 가장 작은 원소를 pop후 return. 비어있는 경우에는 IndexError가 호출된다.
• heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환시킨다.

기본저긍로 heapq 모듈은 최소힙 자료구조를 기반으로 진행됨.

따라서 최소힙을 잘 수정해서 최대힙으로 만들어주어야함.

 

1. 최소힙

• 부모 노드의 키값이 자식 노드의 키값보다 항상 작거나 같은 크기의 관계
• 부모 노드의 키값 ≤ 자식 노드의 키값의 관계를 가지는 노드들의 완전 이진 트리

 

 

예제문제

 

import heapq as hq
a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0: # 숫자 0이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a)) # heappop 함수가 a에서 root노드 값을 pop하여 반환해줌
    else: # 0 이 아닌 숫자는 push
        hq.heappush(a, n) # a라는 리스트에 n값을 넣는다.

입출력 결과

 

 

2. 최대힙

• 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 크기의 관계
• 부모 노드의 키값 >= 자식 노드의 키값의 관계를 가지는 노드들의 완전 이진 트리

최소힙 자료구조에서 마이너스(-)부호를 넣으면 최대힙이 된다!

 

 

import heapq as hq
a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0: # 숫자 0이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a)) # 부호가 반대로해서 push가 됐으니 출력할 때도 -를 붙여줌
    else: # 0 이 아닌 숫자는 push
        hq.heappush(a, -n) # a라는 리스트에 n값을 넣는다.