- 우선순위 큐(Priority Queue)
- 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
- 우선순위 큐는 일반적으로 힙(Heap)을 이용해 구현한다.
- 힙(Heap)
- 완전 이진 트리의 일종으로, 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 반 정렬 상태로, 중복값을 허용한다.
- 최대 힙
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 작은 이진 트리
- 최소 힙
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 이진 트
- 구현 방법
- 우선, 다음이 성립한다.
- 왼쪽 자식 index = (부모 index) * 2
- 오른쪽 자식 index = (부모 index) * 2 + 1
- 부모 index = (자식 index) / 2
- 삽입(push)
- 새로운 요소가 들어오면, 부모 노드와 크기를 비교하여 swap 반복
void insert_max_heap(int x) {
maxHeap[++heapSize] = x;
// 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
for( int i = heapSize; i > 1; i /= 2) {
// 마지막 노드가 자신의 부모 노드보다 크면 swap
if(maxHeap[i/2] < maxHeap[i]) {
swap(i/2, i);
} else {
break;
}
}
}- 우선, 루트 노드가 최댓값이므로 루트 노드를 삭제한다.
- 그 후, 왼쪽 노드와 오른쪽 노드와 크기를 비교하며 swap을 반복한다.
int delete_max_heap() {
if(heapSize == 0) // 배열이 비어있으면 리턴
return 0;
int item = maxHeap[1]; // 루트 노드의 값을 저장
maxHeap[1] = maxHeap[heapSize]; // 마지막 노드 값을 루트로 이동
maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드 0 초기화
for(int i = 1; i*2 <= heapSize;) {
// 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝
if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
break;
}
// 왼쪽 노드가 더 큰 경우, swap
else if (maxHeap[i*2] > maxHeap[i*2+1]) {
swap(i, i*2);
i = i*2;
}
// 오른쪽 노드가 더 큰 경우
else {
swap(i, i*2+1);
i = i*2+1;
}
}
return item;
}Share article
