우선순위 큐(Priority Queue) : 힙(Heap)

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

 

힙(Heap)

• 우선 순위 큐를 구현하기 위해 사용하는 자료 구조 중 하나
• 최소 힙(Min Heap)과 최대 힙(Max Heap) 이 있다.
• 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.

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

 

힙 라이브러리 사용 예제 : 최소 힙

import heapq
# 오름차순 힙 정렬
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
    
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

 

힙 라이브러리 사용 예제 : 최대 힙

import heapq
# 내림차순 힙 정렬
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
    
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)