[자료구조] 우선순위 큐(Priority Queue)
1. 우선순위 큐 - 우선순위 큐는 각 원소들이 우선순위를 갖고 있는 추상 자료형이다. - FIFO 구조를 갖는 큐와 다르게 우선순위 큐는 들어온 순서와 상관없이 우선순위가 높은 원소가 먼저 나간다. - 원소를 추가하거나 제거할 때 우선순위를 갖고 수행해야 한다. - 우선순위 큐와 힙은 같지 않다. 우선순위 큐는 힙 외에도 배열이나 연결 리스트로도 구현 가능하다. - 배열을 이용해 우선순위 큐를 구현하면 삽입할 때 최악의 경우 시간 복잡도가 O(N)이 된다. (추가하는 위치 이후에 있는 모든 원소들을 뒤로 한 칸씩 옮겨줘야 하기 때문에) - 연결리스트로 구현할 때도 삽입 위치를 찾을 때 최악의 경우 O(N)이 소요되기 때문에 배열이나 연결 리스트보다는 힙을 이용한 우선순위 큐가 훨씬 효율적이다. 2. 힙..
