우선순위큐(Priority Queue)

일반적인 큐에서 값을 정렬(내림차순)하고 싶을 때 쓸 수 있는 방법이 우선순위큐다.

이 우선순위큐의 작동 방식은 이진트리의 힙알고리즘으로 진행된다.

​

삽입 : 가장 끝 자식 노드에 삽입 되어 부모와 자신의 값을 비교하여 크다면 올라가고 작다면 그 곳에 머무른다.

​

삭제: 부모노드를 먼저 pop한 후(최대값), 큐의 가장 끝 노드를 부모에 삽입 후 역으로 값을 자식과 비교하며 내려간다. 부모의 값보다 자식노드의 값이 클 경우 교체를 한다. 만약 부모노드보다 자식노드 두개가 더 클 경우

자식 노드 중 큰 값과 부모노드가 교체된다.

​

힙 알고리즘의 개념을 잘 알수있다면 우선순위큐의 작동방식을 이해하기 쉽다.