우선 순위 큐 | Priority-Queue
- 우선 순위 큐는 일반 큐 또는 스택 데이터 구조와 비슷하지만 각 요소에 연결된 "우선 순위"가 있는 추상 데이터 유형임
- 우선 순위 큐에서는 우선 순위가 높은 요소가 낮은 요소 앞에 제공됩니다. 두 요소의 우선순위가 같은 경우 대기열에서 순서에 따라 제공됨
- 우선 순위 큐는 종종 힙을 사용하여 구현되지만 개념적으로 힙과 구별됨
- 우선 순위 큐는 "list" 또는 "map"과 같은 추상 개념임
- 리스트가 연결 리스트나 배열을 사용하여 구현될 수 있듯이 우선 순위 대기열도 힙이나 정렬되지 않은 배열과 같은 다양한 다른 방법으로 구현할 수 있음
최소 힙을 통한 우선 순위 큐 구현
- 최소 힙의 경우 요소의 값을 비교하여 프로세스를 실행했지만,
우선 순위 큐는 map 형태의 priorities 확인하여 프로세스 실행
- 최소 힙
: 비교 시, 값을 보고 더 작은 수를 위로 올리고 큰 수를 아래로 내림 - 우선 순위 큐
: 비교 시, priorities map을 확인 후 우선 순위가 높은(숫자가 낮은) 요소를 위로 올림
Github | javascript-algorithms | trekhleb
changePriority등의 메서드는 위 링크 참조
export default class PriorityQueue {
constructor() {
if (new.target === Heap) {
throw new TypeError('Cannot construct Heap instance directly');
}
// 힙을 배열로 표현함
this.heapContainer = [];
this.priorities = new Map();
}
// 왼쪽 자식의 인덱스 = 부모의 인덱스 *2 + 1
getLeftChildIndex(parentIndex) {
return (2 * parentIndex) + 1;
}
// 오른쪽 자식의 인덱스 = 부모의 인덱스 *2 + 2
getRightChildIndex(parentIndex) {
return (2 * parentIndex) + 2;
}
// 부모의 인덱스 = ((자식의 인덱스 -1) / 2 ))의 내림값
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0;
}
hasLeftChild(parentIndex) {
return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
}
hasRightChild(parentIndex) {
return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
}
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)];
}
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)];
}
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)];
}
swap(indexOne, indexTwo) {
const tmp = this.heapContainer[indexTwo];
this.heapContainer[indexTwo] = this.heapContainer[indexOne];
this.heapContainer[indexOne] = tmp;
}
peek() {
if (this.heapContainer.length === 0) {
return null;
}
return this.heapContainer[0];
}
poll() {
if (this.heapContainer.length === 0) {
return null;
}
if (this.heapContainer.length === 1) {
return this.heapContainer.pop();
}
const item = this.heapContainer[0];
// 마지막 요소를 끝에서 맨 위로 올림
this.heapContainer[0] = this.heapContainer.pop();
this.heapifyDown();
return item;
}
add(item, priority = 0) {
this.priorities.set(item, priority);
this.heapContainer.push(item);
this.heapifyUp();
return this;
}
remove(item) {
// 삭제해야할 아이템의 갯수를 파악
const numberOfItemsToRemove = this.find(item).length;
for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
// heapify 프로세스 후 인덱스가 변경되기 때문에
// 삭제 후 매번 삭제할 요소의 인덱스를 찾아야함
const indexToRemove = this.find(item).pop();
// 마지막 요소를 삭제해야할 경우 heapify가 필요하지 않음
if (indexToRemove === (this.heapContainer.length - 1)) {
this.heapContainer.pop();
} else {
// Move last element in heap to the vacant (removed) position.
// 마지막 요소를 삭제하는 것이 아닌 경우
// 삭제하려는 요소의 자리에 마지막 요소의 값을 할당함
this.heapContainer[indexToRemove] = this.heapContainer.pop();
// 부모 요소를 찾음
const parentItem = this.parent(indexToRemove);
// Max heap의 경우
// 부모 요소가 없거나 부모 요소가 현재 요소값보다 크면 heapify down
// 그 외의 경우 heapify up
if (
this.hasLeftChild(indexToRemove)
&& (
!parentItem
|| this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
)
) {
this.heapifyDown(indexToRemove);
} else {
this.heapifyUp(indexToRemove);
}
}
}
this.priorities.delete(item);
return this;
}
// 기존 Min heap에서는 같은 값을 가진 index를 찾아 배열로 반환했지만,
// 우선 순위 큐에서는 priority가 같은 경우를 찾아 배열로 반환함
find(item) {
const foundItemIndices = [];
for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
if (this.priorities.get(item) === this.priorities.get(this.heapContainer[itemIndex])) {
foundItemIndices.push(itemIndex);
}
}
return foundItemIndices;
}
isEmpty() {
return !this.heapContainer.length;
}
toString() {
return this.heapContainer.toString();
}
heapifyUp(customStartIndex) {
// 힙 컨테이너의 마지막 요소를
// 상위 요소에 대해 올바른 순서가 될 때까지 위로 올림
let currentIndex = customStartIndex || this.heapContainer.length - 1;
// 부모 요소가 존재하고
// && 부모 요소의 값과 현재 값을 비교해서 바꿔야 하는 상황이면 Swap
// Swap을 했을 경우 현재 인덱스를 부모 인덱스로 업데이트
while (
this.hasParent(currentIndex)
&& !this.pairIsInCorrectOrder(
this.parent(currentIndex), this.heapContainer[currentIndex]
)
) {
this.swap(currentIndex, this.getParentIndex(currentIndex));
currentIndex = this.getParentIndex(currentIndex);
}
}
heapifyDown(customStartIndex = 0) {
// head부터 시작해서 부모 요소와 자식 요소를 비교 후
// 올바른 순서가 될 때까지 아래로 내림
let currentIndex = customStartIndex;
let nextIndex = null;
while (this.hasLeftChild(currentIndex)) {
if (
this.hasRightChild(currentIndex)
&& this.pairIsInCorrectOrder(
this.rightChild(currentIndex), this.leftChild(currentIndex)
)
) {
// Max heap의 경우
// 왼쪽 자식과 오른쪽 자식 모두 있고
// 오른쪽 자식이 왼쪽 자식보다 클 경우
// 다음 인덱스는 오른쪽 자식으로 설정
nextIndex = this.getRightChildIndex(currentIndex);
} else {
// 왼쪽 자식이 있는 상황에서
// 오른쪽 자식이 없거나
// 오른쪽 자식이 있어도, 오른쪽 자식이 왼쪽 자식보다 작거나 같을 경우
// 다음 인덱스는 왼쪽 자식으로 설정
nextIndex = this.getLeftChildIndex(currentIndex);
}
// Max heap의 경우
// 현재 인덱스의 값이 다음 인덱스의 값보다 클 경우 => break
if (this.pairIsInCorrectOrder(
this.heapContainer[currentIndex],
this.heapContainer[nextIndex],
)) {
break;
}
// Max heap의 경우
// 현재 인덱스의 값이 다음 인덱스의 값보다 작거나 같을 경우 => swap
this.swap(currentIndex, nextIndex);
currentIndex = nextIndex;
}
}
pairIsInCorrectOrder(firstElement, secondElement) {
// Min Heap일 경우
// 첫번째 인자가 두번째 인자보다 크거나 같아야함.
// 그 반대의 경우 incorrect = true
return firstElement < secondElement
}
}📚 참고
Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Photo by Alain Pham on Unsplash
protect me from what i want