일반적인 큐에서 값을 정렬(내림차순)하고 싶을 때 쓸 수 있는 방법이 우선순위큐다.
이 우선순위큐의 작동 방식은 이진트리의 힙알고리즘으로 진행된다.
삽입 : 가장 끝 자식 노드에 삽입 되어 부모와 자신의 값을 비교하여 크다면 올라가고 작다면 그 곳에 머무른다.
삭제: 부모노드를 먼저 pop한 후(최대값), 큐의 가장 끝 노드를 부모에 삽입 후 역으로 값을 자식과 비교하며 내려간다. 부모의 값보다 자식노드의 값이 클 경우 교체를 한다. 만약 부모노드보다 자식노드 두개가 더 클 경우
자식 노드 중 큰 값과 부모노드가 교체된다.
힙 알고리즘의 개념을 잘 알수있다면 우선순위큐의 작동방식을 이해하기 쉽다.
'TIL > 알고리즘 개념' 카테고리의 다른 글
| 약수를 효율적으로 구하는 방법 (0) | 2023.09.06 |
|---|---|
| Big-O 표기법 (0) | 2023.08.16 |
| 그래프(Graph) (0) | 2023.08.16 |
