[이론] 우선순위 큐 Priority Queue

우선순위 큐

Heap

우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나입니다. 최소 힙과 최대 힙이 있습니다.

우선순위 큐 구현 방식	삽입	삭제
list	O(1)	O(N)
Heap	O(logN)	O(logN)

Sort with min heap

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) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Success Notice: 수고하셨습니다.