자바스크립트로 코딩 테스트 문제를 풀면 우선순위 큐를 사용할 시간이 오게 된다.
하지만 아쉽게도 자바스크립트는 직접 코드를 작성해야 한다. 🥲 우선순위 큐를 알아보기 전에 우선순위 큐는 힙으로 되어있다.
그렇기 떄문에 근본인 힙을 알아야 한다. 힙부터 알아보자.
힙이란?
트리 구조의 일종으로 이진 트리와 비슷해 보이지만 다르며, 최대 이진 힙, 최소 이진 힙이 있다.
힙이랑 이진 힙이랑 같다고 보명 된다. 😀
힙은 이것만 알면 된다능~
최대 이진 힙 기준
1. 트리의 루트는 최대 값이다.
2. 자식 노드는 항상 부모노드보다 작다.
3. 자식 노드는 순서가 없다. -> 이진트리랑 핵심 차이이다.
4. 최대 2개의 자식노드를 가질 수 있다.
이것만 알면 끝이다.
아래 사진은 이진트리와 최대 이진 힙의 차이다.
이진트리는 자식 노드가 부모보다 작으면 항상 왼쪽에 있고 크면 오른쪽에 있지만 최대 이진 힙은 그딴 게 없다.
본격적으로 힙의 메서드들을 알아보기 전 힙의 마법만 알아보자 이것만 알면 구현가능
힙의 왼쪽 자식 노드의 인덱스는 부모의 index * 2 + 1이고 오른쪽 자식 노드의 인덱스는 부모의 index * 2 + 2이다.
반대로 힙의 부모 노드의 위치는 (자식노드의 인덱스 - 1)/2를 구하면 알 수 있다.
아래 사진에서 핑크 선으로 칠한 부분을 보면 5의 자식 노드는 1과 4이다. 이것을 위의 마법에 대입해 보면 5의 인덱스는 6이므로
6 * 2 + 1 = 13, 6 * 2 + 2 = 14로 13과 14는 왼쪽 자식과 오른쪽 자식의 인덱스를 가리키고 있다. 또 반대로 (13 - 1)/2, (14 - 1)/2를
해주면 부모 노드의 인덱스를 알 수 있다. 소수점은 버리면 된다. 이 마법의 원리만 알면 힙 구현은 씹가능이다. 지나가는 고양이도 구현 가능
힙은 4가지 기능만 구현하면 끝 insert, bubbleUp, extractMax, sinkDown 이것만 구현하면 된다.
그럼 하나하나씩 알아보자.
힙은 배열로 되어있는데 데이터를 삽입하려면 insert, bubbleUp이 필요하다. 이걸 구현하기 전에 과정을 봐보자.
최대 이진 힙에서 55를 삽입해서 과정을 알아볼 것이다.
1. 우선 마지막에 55를 넣는다.
55를 넣은 후 힙의 배열
2. 자식의 부모 노드와 비교 후 부모 노드보다 크면 자리를 바꾼다. 이것이 bubbleUp이다.
-> 여기서 아까 알아본 마법을 사용하면 된다.(힙의 부모 노드의 위치는 (자식노드의 인덱스 - 1)/2를 구하면 알 수 있다.)
3. 자신 보다 부모 노드가 큰 게 확인될 때까지 2번 과정을 반복하면 된다.
이제 코드로 insert와 bubbleUp을 봐보자.
insert(element) {
this.values.push(element);
this.bubbleUp();
}
bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.values[parentIdx];
if (element <= parent) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
아래는 코드에 대한 설명이다.
이제 마지막 extractMax와 sinkDown만 알면 다 끝난다.
추출하는 과정을 봐봅시다.
아래 사진에서 루트를 제거할 거예요. 왜? 최대 이진 힙은 루트가 최댓값이기 때문
1. 루트를 제거한다. 그리고 배열의 제일 마지막에 있는 값을 루트에 가져옵니다.
2. 이제 bubbleUp과 반대로 자식노드와 비교해서 자식노드 보다 작으면 바꿔줍니다. 이걸 반복하면 됨(sinkDown과정)
-> 여기서 아까 알아본 마법을 사용합니다.
(힙의 왼쪽 자식 노드의 인덱스는 부모의 index * 2 + 1이고 오른쪽 자식 노드의 인덱스는 부모의 index * 2 + 2이다.)
반복을 마친 후
요약
1. 루트 값을 제거한다.
2. 배열의 가장 끝에 있는 값을 루트로 가져온다.
3. 이제 루트가 된 값을 자식 노드와 비교해서 자식이 부모보다 크면 바꿔준다.(단 자식 노드가 둘 다 크면 가장 큰 자식과 바꿔줘야 합니다.)
4. 3번의 과정을 반복한다.
여기서 이것만 알면 이제 끝! 루트가 된 값을 자식 노드와 비교해서 자식이 부모보다 크면 바꿔준다.(단 자식 노드가 둘 다 크면 가장 큰 자식과 바꿔줘야합니다.)
아래 코드는 위의 과정의 코드입니다. 진짜 이것만 알면 됨
extractMax() {
const max = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return max;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild > element) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}코드에 대한 설명
전체 코드
class MaxBinaryHeap {
constructor() {
this.values = [];
}
insert(element) {
this.values.push(element);
this.bubbleUp();
}
bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.values[parentIdx];
if (element <= parent) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
extractMax() {
const max = this.values[0]; // 최대값을 뽑음
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end; // 배열의 가장 마지막 값을 루트로 이동
this.sinkDown(); // 루트와 자식노드를 비교하는 메서드
}
return max;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
let leftChildIdx = 2 * idx + 1; // 자식 노드 인덱스를 찾는 마법 (왼쪽 자식)
let rightChildIdx = 2 * idx + 2;// 자식 노드 인덱스를 찾는 마법 (오른쪽 자식)
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild > element) { // 왼쪽 자식이 더 크면 스왑할 대상에 지정
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if (
(swap === null && rightChild > element) || //왼쪽 자식이 부모 보다 더작은데 오른쪽 자식은 부모 보다 크거나
(swap !== null && rightChild > leftChild) // 왼쪽 자식이 큰데 오른쪽 자식이 더크면 스왑할 대상에 지정
) {
swap = rightChildIdx;
}
}
if (swap === null) break; // 자식 둘다 안크면 그만둬버리기~
this.values[idx] = this.values[swap]; // 스왑할 자식과 자리 교환
this.values[swap] = element;
idx = swap;
}
}
}수고하셨습니다. 이제 당신은 힙을 할 수 있게 됐습니다.
마지막으로 위의 그림 과정을 실행시켜봅시다. [41, 39, 33, 18, 27, 12]에서 55를 추가 후 두 번 추출하면 위에서 봤던 그림과 같이 될 겁니다.
지나가던 고양이도 할 수 있는 힙이었습니다. 솔직히 안 보고 저도 못함 ㅠ 까먹어서 올린 거는 비밀💩
참고자료 유데미 자료구조 마스터 클래스 https://hanium.udemy.com/course/best-javascript-data-structures