공부(Archive)/Data structure
-
우선순위 큐(Priority queue)공부(Archive)/Data structure 2019. 6. 12. 12:40
우선순위 큐는 큐와 같이 FIFO와 비슷한 특징을 갖는다. 다른 점이 있다면 큐에 있는 원소를 처리할 때 가장 먼저 들어온 원소를 먼저 처리하는 것이 아닌 우선순위가 가장 높은 원소가 빠져나간다. 따라서 우선순위 큐에 저장되는 원소들은 모두 우선순위를 갖는다. 얼마 전까지 우선순위 큐는 항상 힙으로 구현되는 줄 알았는데 검색을 해보며 찾아보니 아니라는 것을 알게 되었다. "우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다; 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다." https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC..