[자료 구조] 우선순위 큐(Priority Queue)와 힙(Heap)

우선선위 큐 (Priority Queue)

---

• 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

▶ 우선순위 큐를 구현하는 방법은 다양하다.

 

   1) 단순히 리스트를 이용하여 구현 가능

   2) 힙(heap)을 이용하여 구현 가능

 

 

▶ 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도 비교

 

힙(Heap)의 특징

---

• 완전 이진 이트 자료구조의 일종
• 힙에서는 항상 루트 노트(rooot node)를 제거 
• 최소힙(min heap) : 루트 노트가 가장 작은 값을 가지는 힙
• 최대힙(max heap) : 루트 노트가 가장 큰 값을 가지는 힙

 

▶ 완전  이진 트리 (Complete Binary Tree)

 

루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미

 

▶ 최소 힙 구성 함수

 

Min-Heapify()

부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다. (상향식)

 

 

▶ 원소 삽입

 

새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

 

 

▶ 원소 제거

 

원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

 

원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함.

이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행

 

 

우선순위 큐 라이브러리를 활용한 힙 정렬 구현 (Python)

---

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])

 

 

 

참고 

https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11