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

목 차 우선순위 큐 최소 힙 시간 복잡도 작동 원리 구현 코드 우선순위 큐 우선순위 큐(Priority Queue)는 말 그대로 우선순위를 가진 요소들을 저장하는 자료구조이다. 우선순위가 가장 높은 요소를 먼저 꺼낼 수 있게 한다. 대표적으로 최소 힙, 최대 힙이 있다. 최소 힙 다익스트라 알고리즘(Dijkstra Algorithm)을 학습하기 전에 우선순위 큐를 배우고 그중에서 최소 힙을 배우기에 이 번에는 최소 힙만 다룰 예정이다. 시간 복잡도 우선순위 큐를 구현하는 방법에는 여러 가지 있지만, 힙(Heap) 자료구조를 사용하는 것이 가장 효율적이고 우선순위가 가장 높은 데이터를 꺼내는데 O(log N) 만큼 걸린다. 작동 원리 1. 삽입(Insert): 새로운 요소는 항상 배열의 마지막에 들어간다(..

Algorithm 2023.10.26