우선순위 큐를 공부하다가 확인할 내용이 있어서 질문드립니다.
뇌를 자극하는 알고리즘 책 p287에 보면 우선순위 큐의 개념에 관하여 설명되어있습니다.
책에는 삽입시에 우선순위를 고려하고 삭제시 고려하지 않는다고 나와있습니다.
ex)
2 17 22 23 56 117 과 같은 우선순위 큐에 20을 삽입한다면...
2 17 20 22 23 56 117 로 삽입이 되어야 한다고 나와있습니다.
그런데, 다른 책이나 인터넷에서 레퍼런스를 찾아보면 해당 경우에
삽입시에는 무조건 가장 앞에 삽입하고 (20 2 17 22 23 56 117)
삭제시에 힙을 이용하여 최소값(최소값이 우선순위라면) 2를 삭제하여
20 17 22 23 56 117와 같이 된다고 나와있습니다.
실제로, 책에 나와있는데로 우선순위를 구현을 해보면, 굳이 힙이 필요한 것 같지가 않습니다.
힙을 이용하는 것은 오로지 최소값이나 최대값을 구하기 위함인데
삽입시 최소값을 알게 됨으로서 어떤 이득을 볼 수 있을지 모르겠습니다.
(우선순위를 고려하여 삭제를 한다면, 힙이 유용하겠지요.)
p.s. 제가 참고한 서적입니다.
제목 : "Fundamentals of Data Structures in C++ 2nd Edition"
저자 : Horowitz Sahni Mehta
번역 : 이석호
확인 부탁드립니다~!