[CS] 자바스크립트로 힙 구현하기

오고 말았다 자료 구조 구현하기

사실 진작부터 왔지만 이 악물고 모른 척 했다는 게 학계의 정설

JS를 쓰면서 굳이 자료 구조를 구현하지 않아도 됐는데 이번에 힙을 만나면서 아 역시 구현을 해보긴 해봐야겠구나 하고 필요성을 느꼈다. 사실 원리만 이해하면 그렇게 죽을 것처럼 어려운 건 아닌데, 클래스에 대해 잘 아는 게 아니다 보니 진입장벽이 있었다. 근데 어처피 해야 하니까 클래스에 대해서도 이해해볼 겸 슬금슬금 다른 분들의 코드를 참고해서 구현해보았다.

 

 

힙은 배열로 구현할 건데, 루트 노드부터 같은 레벨의 왼쪽 노드 -> 오른쪽 노드 순으로 push한다. 즉 [10, 9, 5, 8, 3, 2, 4, 6, 7, 1] 순으로 채워지며 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드는 위 표와 같이 구할 수 있다.

 

최대 힙 구현하기

1. MaxHeap 선언과 스왑

class MaxHeap {
  constructor() {
    this.data = [];
  }

  swap(index1, index2) {
    let temp = this.data[index1];
    this.data[index1] = this.data[index2];
    this.data[index2] = temp;
  }

빈 배열을 선언한다. swap을 통해 두 값을 바꿔줄 때는 임시 변수 temp을 사용한다.

 

2. 부모 노드의 인덱스와 값, 자녀 인덱스와 값

  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChildIndex(index) {
    return index * 2 + 1;
  }

  rightChildIndex(index) {
    return index * 2 + 2;
  }

  parent(index) {
    return this.data[this.parentIndex(index)];
  }

  leftChild(index) {
    return this.data[this.leftChildIndex(index)];
  }

  rightChild(index) {
    return this.data[this.rightChildIndex(index)];
  }

위 이미지에서 보았던 것처럼 부모 노드의 인덱스와 값, 자녀 노드의 인덱스와 값을 구한다. 왼쪽 자식 노드와 오른쪽 자식 노드를 구할 때는 인덱스가 1 차이 나는 것을 기억하자.

 

3. insert와 bubbleUp()

  insert(value) {
    this.data.push(value);
    this.bubbleUp();
  }

bubbleUp() {
    let index = this.data.length - 1;

    while (
      this.parent(index) !== undefined &&
      this.parent(index) < this.data[index]
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

데이터가 들어올 때에는 가장 끝에 들어온다. 가장 끝에 들어온 데이터의 인덱스를 기준으로 값을 비교해 나가려고 한다. 현재 index는 가장 끝에 들어온 데이터다. 부모 노드가 존재하면서 그 값이 비교하려는 노드의 값보다 작다면 swap이 이루어진다. 그래서 부모 노드와 현재 비교하는 노드의 값과 인덱스를 모두 교환해준다.

 

4. extract와 bubbleDown()

extract() {
    const max = this.data[0];
    if (this.data.length === 1) {
      this.data.pop();
      return max;
    }
    this.data[0] = this.data.pop();
    this.bubbleDown();
    return max;
  }

먼저 최댓값을 추출하는 경우, 최댓값은 max로 배열의 제일 왼쪽에 위치할 것이다. 이 때 배열의 길이가 1이라면 === 최댓값 하나밖에 없다면 최댓값 하나를 추출하고 끝낸다. 만약 길이가 1보다 크다면 최댓값을 추출한 후 그 빈자리를 채우기 위해 bubbleDown()이 실행된다.

 

bubbleDown() {
    let index = 0;

    while (
      this.leftChild(index) !== undefined &&
      (this.leftChild(index) > this.data[index] ||
        this.rightChild(index) > this.data[index])
    ) {
      let largerIndex = this.leftChildIndex(index);

      if (
        this.rightChild(index) !== undefined &&
        this.rightChild(index) > this.data[largerIndex]
      ) {
        largerIndex = this.rightChildIndex(index);
      }
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }

인덱스 0부터 비교를 시작한다. (완전 이진 트리기 때문에 왼쪽을 기준으로 비교하고 오른쪽이 있으면 왼쪽과 오른쪽을 비교한다.) 우선 왼쪽 자식 노드가 존재하고, 왼쪽 자식 노드의 값이 현재 0번째 노드의 값보다 크거나 오른쪽 자식 노드의 값이 현재 0번재 노드의 값보다 클 경우 일단 가장 큰 인덱스를 왼쪽 자식 노드로 설정한다. 이를 통해 더 큰 값을 가진 녀석들이 부모 노드와 바뀌어 위로 가게 된다.

 

class MaxHeap {
  constructor() {
    this.data = [];
  }

  swap(index1, index2) {
    let temp = this.data[index1];
    this.data[index1] = this.data[index2];
    this.data[index2] = temp;
  }

  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChildIndex(index) {
    return index * 2 + 1;
  }

  rightChildIndex(index) {
    return index * 2 + 2;
  }

  parent(index) {
    return this.data[this.parentIndex(index)];
  }

  leftChild(index) {
    return this.data[this.leftChildIndex(index)];
  }

  rightChild(index) {
    return this.data[this.rightChildIndex(index)];
  }

  peek() {
    return this.data[0];
  }

  size() {
    return this.data.length;
  }

  bubbleUp() {
    let index = this.data.length - 1;

    while (
      this.parent(index) !== undefined &&
      this.parent(index) < this.data[index]
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  bubbleDown() {
    let index = 0;

    while (
      this.leftChild(index) !== undefined &&
      (this.leftChild(index) > this.data[index] ||
        this.rightChild(index) > this.data[index])
    ) {
      let largerIndex = this.leftChildIndex(index);

      if (
        this.rightChild(index) !== undefined &&
        this.rightChild(index) > this.data[largerIndex]
      ) {
        largerIndex = this.rightChildIndex(index);
      }
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }

  insert(value) {
    this.data.push(value);
    this.bubbleUp();
  }

  extract() {
    const max = this.data[0];
    if (this.data.length === 1) {
      this.data.pop();
      return max;
    }
    this.data[0] = this.data.pop();
    this.bubbleDown();
    return max;
  }
}

const max = new MaxHeap();

max.insert(5);
max.insert(10);
max.insert(15);
max.insert(20);
max.insert(25);

console.log(max); // MaxHeap { data: [ 25, 20, 10, 5, 15 ] }

console.log(max.extract()); // 25
console.log(max.extract()); // 20
console.log(max.extract()); // 15
console.log(max.extract()); // 10
console.log(max.extract()); // 5
console.log(max); // MaxHeap { data: [] }

 

최소 힙 구현하기

최대 힙 구현 코드의 부등호를 모두 반대로 바꿔주면 된다.

class MinHeap {
  constructor() {
    this.data = [];
  }

  swap(index1, index2) {
    let temp = this.data[index1];
    this.data[index1] = this.data[index2];
    this.data[index2] = temp;
  }

  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChildIndex(index) {
    return index * 2 + 1;
  }

  rightChildIndex(index) {
    return index * 2 + 2;
  }

  parent(index) {
    return this.data[this.parentIndex(index)];
  }

  leftChild(index) {
    return this.data[this.leftChildIndex(index)];
  }

  rightChild(index) {
    return this.data[this.rightChildIndex(index)];
  }

  peek() {
    return this.data[0];
  }

  size() {
    return this.data.length;
  }

  bubbleUp() {
    let index = this.data.length - 1;

    while (
      this.parent(index) !== undefined &&
      this.parent(index) > this.data[index]
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  bubbleDown() {
    let index = 0;

    while (
      this.leftChild(index) !== undefined &&
      (this.leftChild(index) < this.data[index] ||
        this.rightChild(index) < this.data[index])
    ) {
      let smallerIndex = this.leftChildIndex(index);

      if (
        this.rightChild(index) !== undefined &&
        this.rightChild(index) < this.data[smallerIndex]
      ) {
        smallerIndex = this.rightChildIndex(index);
      }
      this.swap(smallerIndex, index);
      index = smallerIndex;
    }
  }

  insert(value) {
    this.data.push(value);
    this.bubbleUp();
  }

  extract() {
    const min = this.data[0];
    if (this.data.length === 1) {
      this.data.pop();
      return min;
    }
    this.data[0] = this.data.pop();
    this.bubbleDown();
    return min;
  }
}

const min = new MinHeap(); // 

min.insert(5);
min.insert(10);
min.insert(15);
min.insert(20);
min.insert(25);

console.log(min); // MinHeap { data: [ 5, 10, 15, 20, 25 ] }

console.log(min.extract()); // 5
console.log(min.extract()); // 10
console.log(min.extract()); // 15
console.log(min.extract()); // 20
console.log(min.extract()); // 25
console.log(min); // MinHeap { data: [] }

 

참고

210627 TIL) 우선순위 큐, 자료구조 heap, 해시

[자바스크립트 자료구조] 힙(Heap) - (1) 최소힙, 최대힙 구현