힙
-
[자료구조] 우선순위 큐(priority_queue)코딩 2021. 7. 15. 12:12
※코딩뉴비가 자신이 이해한대로 쓴 글이라 정확하지 않은 정보가 담겨있을 수 있습니다. 우선순위 큐란? 자신이 정해놓은 우선순위대로 넣었던 원소가 나오는 자료구조 우선순위 큐의 구현 우선순위 큐는 주로 힙(Heap)이라는 자료 구조로 구현합니다. 왜일까요? 삽입과 삭제에 대한 효율이 좋기 때문입니다. 배열로 우선순위 큐를 구현할 경우, 우선순위에 따라서 배열을 정렬해놓아 사용할 수 있습다. 그러면 가장 우선순위가 높은 원소를 삭제할 때에는 가장 앞의 원소를 삭제하면 되므로 O(1)의 시간복잡도가 걸립니다. 다만, 삽입 과정에서 최악의 경우 모든 원소와 하나하나 비교해야 하기 때문에 O(N)의 시간복잡도가 걸립니다. 연결 리스트로도 비슷하게 생각할 때 삽입은 O(N), 삭제는 O(1)이 걸립니다. 그..