Priority Queue
우선순위 큐는 데이터를 저장하는 자료구조 중 하나로 각 요소에 우선순위를 할당하고 그 우선순위에 따라 요소들을 정렬하는 자료구조입니다.
우선순위가 가장 높은 요소가 항상 첫번째 인덱스에 위치해 있으며 삽입 시점에 상관없이 가장 먼저 제거됩니다.
또한 두 요소의 우선순위가 동일한 경우 순서에 따라 제거됩니다.
Heap
힙이란 각 노드의 값이 특정한 우선순위 규칙을 따르는 자료구조입니다.
힙은 이진 트리로 구성되며 각 노드는 최대 두개의 자식 노드를 가질 수 있습니다.
일반적으로 힙은 보통 완전 이진 트리의 형태를 가지며 왼쪽부터 차례대로 노드가 채워집니다.
최소 힙
각 노드의 값은 그 자식 노드의 값보다 작거나 같은 힙으로 루트 노드가 가장 작은 값을 가집니다.
최대 힙
각 노드의 값은 그 자식 노드의 값보다 크거나 같은 힙으로 루트 노드가 가장 큰 값을 가집니다.
Heapify
Heapify는 힙을 고친다라는 의미로 현재 삽입 혹은 삭제될 노드에 의해 전체 정렬 상태에 영향이 생길 경우 그 정렬을 다시 올바르게 진행하기 위한 절차를 의미합니다.
현재 노드보다 상단으로 힙을 고쳐야 한다면 Above Heapify, 하단으로 힙을 고쳐야 한다면 Below Heapify 라고 부릅니다.
삽입
힙은 데이터 삽입 시 우선순위에 따라 저장되는 노드의 위치가 달라집니다.
즉 삽입된 트리의 가장 마지막 노드에서 힙의 성질을 유지하기 위한(값의 우선 순위) 위해 상향식으로 부모 노드로 거슬러 올라가며 값 비교 후 적절한 위치로 교체하기 위해 Above Heapify 방식으로 동작합니다.
가장 마지막 노드 삽입된 값은 그 부모의 노드와 값을 계속적으로 비교하며 위치를 교체합니다.
삭제
가장 우선순위가 높은 노드를 삭제할 때 루트 노드를 삭제하고 힙의 마지막 노드를 루트 노드로 옮긴 후 힙의 성질을 유지하기 위해 자식 노드와 비교하면서 값을 조정합니다.
대체된 루트 노드로부터 자식 노드들의 값을 하향식으로 비교하며 힙의 재정렬이 이루어짐으로 Above Heapify 방식으로 동작합니다.
시간 복잡도
| 연산 | 최대 힙(Max Heap) | 최소 힙(Min Heap) |
|---|---|---|
| 삽입 | O(log N) | O(log N) |
| 삭제 | O(log N) | O(log N) |
| 조회 | O(1) | O(1) |
각 연산의 시간 복잡도는 기본적으로 O(log N)의 시간 복잡도를 갖습니다.
일반적으로 힙은 완전 이진 트리로 구성되므로 힙의 높이는 log N에 근사한 값을 가집니다.
따라서 삽입과 삭제 연산의 경우 O(log N)의 시간 복잡도를 갖습니다.
조회(Peek) 연산은 단순히 루트 노드를 반환하기 때문에 O(1)의 시간 복잡도를 가집니다.
오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.