- 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
* 해당 자료는 '동빈나'님의 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약 영상을 토대로 정리한 내용임을 밝힙니다.
https://www.youtube.com/watch?v=AjFlp951nz0
* 또한 코드로 구현한 부분은 https://velog.io/@ssh1997/JavaScript-%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%9C-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue 해당 블로그를 참조했음을 밝힙니다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우
구현방법
- 리스트
- 힙(Heap)
시간복잡도 (구현방법에 따라)
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)
- 이 경우 시간 복잡도는 O(NlogN)입니다.
힙(Heap)의 특징
- 힙은 완전 이진 트리 자료구조의 일종입니다.
- 힙에서는 항상 루트 노드(root node)를 제거합니다.
- 최소 힙(min heap)
1. 루트 노드가 가장 작은 값을 가집니다.
2. 따라서 값이 작은 데이터가 우선적으로 제거됩니다. - 최대 힙(max heap)
1. 루트 노드가 가장 큰 값을 가집니다.
2. 따라서 값이 큰 데이터가 우선적으로 제거됩니다.
<최소 힙의 예시>
완전 이진 트리 (Complete Binary Tree)
루트(root) 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미합니다.
최소 힙 구성 함수: Min-Heapify()
(상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체합니다.
힙에 새로운 원소가 삽입될 때 (enQueue())
힙에서 원소가 제거될 때 (deQueue())
1. 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다.
2. 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) swap()를 진행합니다.
class Queue {
data = [];
// firstIndex = 0;
enQueue = (data) => {
this.data.push(data);
};
deQueue = () => {
return this.data.shift();
// 이 부분이 O(n) 의 시간이 걸리는게 문제일수도 있어서
// 맴버변수로 firstIndex를 저장하며
// return this.data[firstIndex++]; 로 대체할 수 도 있겠다.
};
}- enQueue( data ) 를 통해 data 를 삽입할 수 있다.
- deQueue( ) 를 통해 첫번째 데이터를 추출할 수 있다.
다음으로 이를 상속받아 메소드들을 선언해 보았다.
class PriorityQueue extends Queue {
enQueue = () => {};
deQueue = () => {};
}구현 - enQueue()
다음으로 재귀적으로 수행할 메소드와 swap 메소드를 선언해 주었다.
인자로는 비교할 데이터와 인덱스를 주어 부모노드의 값에도 접근할 수 있게 했다.
class PriorityQueue extends Queue {
swap = (a, b) => {
const temp = this.data[a];
this.data[a] = this.data[b];
this.data[b] = temp;
};
compareBottomUp = (data, index) => { // 상향식 우선순위 비교
const parentIndex = Math.floor((index - 1) / 2); // 나머지 버림으로 부모 노드 index 유추
if (this.data[parentIndex] < data) {
this.swap(index, parentIndex);
this.compareBottomUp(data, parentIndex);
}
};
enQueue = (data) => {
this.data.push(data);
this.compareBottomUp(data, this.data.length - 1);
};
}
const priorityQueue = new PriorityQueue();
priorityQueue.enQueue(1);
priorityQueue.enQueue(2);
priorityQueue.enQueue(3);
console.log(priorityQueue.data);
// output : [3, 1, 2]결과
구현 - deQueue ( )
class PriorityQueue extends Queue {
:
:
compareTopDown = (data, index) => { // 하향식 우선순위 비교
const childIndexBase = index * 2;
let target = childIndexBase + 1;
if (this.data[childIndexBase + 1] < this.data[childIndexBase + 2]) {
target += 1;
} // 좌, 우 자식 노드 중 큰 노드를 선택
if (this.data[target] > data) {
this.swap(target, index);
this.compareTopDown(data, target);
}
};
deQueue = () => {
const result = this.data[0];
const data = this.data.pop();
this.data[0] = data; // shift() 는 O(n) 이므로 마지막 노드를 pop( ) 하여 치환
this.compareTopDown(data, 0);
return result;
};
}
const priorityQueue = new PriorityQueue();
priorityQueue.enQueue(1);
priorityQueue.enQueue(2);
priorityQueue.enQueue(3);
priorityQueue.enQueue(4);
priorityQueue.enQueue(3);
priorityQueue.enQueue(1);
console.log(priorityQueue.deQueue());
// output : 4
console.log(priorityQueue.data);
// output : [3, 3, 2, 1, 1]