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

✅우선순위 큐란?

우선순위가 가장 높은 데이터를 먼저 삭제하는 구조

- 가장 먼저 삽입된 데이터를 삭제하는 일반적인 큐(Queue)와 다르다. 

우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용

 

✅우선순위 큐 구현방식

1) 리스트

   리스트에서 인덱싱해서 꺼내는 방식. 리스트 자료형을 그대로 사용. 

2) 힙(heap)

 

각 방식의 시간 복잡도

우선순위 큐 구현 방식	삽입시간	삭제시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

 

✅힙(heap)

힙은 완전 이진 트리 자료 구조의 일종

* 완전 이진 트리 자료구조란?

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

 

힙의 방식

1) 최소 힙

  : 루트 노드가 가장 작은 값을 가짐

    값이 작은 데이터가 우선적으로 제거

 

2) 최대 힙

  : 루트 노드가 가장 큰 값을 가짐

    값이 큰 데이터가 우선적으로 제거 

[최소 힙 구성 함수: Min-Heapify()] 

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

 

- 새로운 원소가 삽입될 때, 자신의 값이 부모보다 더 작을 때 부모노드로 거슬로 올라감. 

- 원소가 제거 될 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함. 이후 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify() 진행

 

✅pythone으로 구현하기

 

heapq를 이용해 최소힙 정렬 구현하기

* 최대 힙은 (-value) 로 대체

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

 

 

Reference

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