🍞 우선순위 큐란?
1) 큐(Queue)란?
선입선출(FIFO - First In Frist Out) 자료구조다.
먼저 들어온 데이터가 먼저 나간다.
2) 우선순위 큐(Priority Queue)란?
우선순위 큐는 선입선출(FIFO)이 아닌, 우선순위(Priority)가 가장 높은 데이터가 먼저 나가는 자료구조다.
우선순위가 가장 높은 데이터가 맨 앞에 있다.
🍞 힙(Heap) 이란?
완전 이진 트리 형태를 기본으로 한다. 최대값이나 최솟값을 찾아내기 위해 고안되었다. 따라서 루트노드는 가장 큰 값이나 가장 작은 값을 가진다.
느슨한 이진트리다. 부모 자식간에 대소관게를 성립하지만, 형제사이는 신경쓰지 않는다.
트리지만 완전 이진트리이기 때문에 배열로 데이터를 저장할 수 있다.
본인 인덱스에서 * 2 + 1 를 하면 왼쪽 자식노드이고, * 2 + 2 을 하면 오른쪽 자식 노드로 바로 이동할 수 있기 때문이다.
이때 인덱스 0은 편의를 위해 건너뜁니다.
배열 뒤에 인덱스가 없으면 undefined이기 때문에 꼭 완전 이진 트리일 필요는 없다. 이진 트리로도 충분하다.
🍞 우선순위 큐 - 힙으로 구현하기
1) 삽입
(1) 방법
1. 우선 힙 배열 마지막에 데이터를 넣습니다.
2. 부모와 비교해서 더 작은 데이터를 부모로 교체하는 연산을 반복합니다.
(2) 자세한 과정
최소값을 구하는 우선순위 큐를 구현하였다.
트리가 위와 같이 있을 때
우선 맨 마지막에 데이터를 넣는다.
부모와 비교를 하고, 더 작은 데이터가 부모로 있을 수 있게 교체한다.
루트노드가 되거나, 부모가 더 작을 때까지 반복한다.
(3) 코드 구현
코드로 구현하면 아래와 같다.
자식의 왼쪽과 오른쪽이 각각 i * 2 +1 와 i * n + 2 이었다면, 부모는 거꾸로 (i - 1) / 2 의 내림값으로 구할 수 있다.
더 작은 값이 있다면 교체한뒤, i를 부모로 바꾼다. 이 과정을 반복한다.
function enqueue(arr, data) {
// 마지막에 추가
arr.push(data);
// 현재 index
let i = arr.length - 1;
// 부모가 없거나, 부모 데이터가 더 작을 때 까지 반복
while (i > 1 && arr[i] < arr[Math.floor((i - 1) / 2)]) {
// 현재 데이터 < 부모 데이터라면 교체
const parent = arr[Math.floor((i - 1) / 2)];
arr[Math.floor((i - 1) / 2)] = arr[i];
arr[i] = parent;
// 현재 index를 부모로
i = Math.floor((i - 1) / 2);
}
}
2) 삭제
(1) 방법
1. index 1에 있는 데이터를 보관합니다.
2. 자식으로 내려가면서 더 작은 데이터를 부모로 교체하는 연산을 반복합니다.
(2) 자세한 과정
가장 앞에 있는 값을 return하기 위해 잠시 보관해둔다.
맨 앞에는 가장 뒤에 있는 값으로 채우고, 가장 뒤에 있는 값은 없애준다.
자식과 비교해서 더 작은 값이 있다면 부모로 교체 해준다.
(3) 코드 구현
코드로 구현하면 아래와 같다.
자식 중에 더 작은 값이 있는지 검사를 한 다음, 왼쪽이 더 작은지 오른쪽이 더 작은지 비교해주었다. 조건문은 구현하는 다른 방법이 많다.
더 작은 값이 있다면 부모로 교체한다. 이 방법을 반복한다.
function dequeue(arr) {
// 1순위 반환 예정
const result = arr[0];
// 맨 마지막 데이터를 부모로 올림
arr[0] = arr[arr.length - 1];
// 맨 마지막 제거
arr.pop();
let i = 0;
// 자식이 더 클 때까지 반복
while (arr[i * 2 + 1] < arr[i] || arr[i * 2 + 2] < arr[i]) {
// 더 작은쪽이
let childIndex = i * 2 + 1; // 왼쪽이냐
if (arr[i * 2 + 1] > arr[i * 2 + 2]) {
//오른쪽이냐
childIndex = i * 2 + 2;
}
// 현재 데이터 > 자식 데이터라면 교체
const child = arr[childIndex];
arr[childIndex] = arr[i];
arr[i] = child;
// 현재 index를 부모로
i = childIndex;
}
return result;
}
https://yoongrammer.tistory.com/81
https://chamdom.blog/heap-using-js/