Heap한 개발자가 되기 위한 Heap

Park.Dyel·2021년 9월 30일

FE

목록 보기

4/6

Heap

프로그래머스 문제를 통해 오랫만에 접한 자료구조 Heap에 대해 살펴보고자 합니다. 이 문서에서는 하나씩 구현하고자 하니, 자료구조 Heap이 궁금하신 분은 이 문서를 참고해보세요.

정렬 기준에 따라 MinHeap과 MaxHeap을 구현해보도록 하겠습니다. 두 자료구조의 공통된 로직은 class Heap에 정의하고, 고유한 로직은 각각의 class에 정의하겠습니다. 먼저 저장공간과 삽입, 추출 함수를 정의하겠습니다.

class Heap {
  constructor () {
    this.memory = [];
  }
  
  push(node){
    this.memory[this.memory.length] = node;
  }

  pop(){
    const node = this.memory[0];
    this.memory[0] = this.memory[this.memory.length - 1];
    this.memory.pop();
    return node;
  }
}

하지만, 위 코드는 class 외부에서 내부 변수인 memory에 접근할 수 있는 문제가 있어, private keyword인 #을 사용하여 memory를 private 변수로 선언해보겠습니다. private에 관한 문법은 이 문서를 살펴보세요. ~~새로운 문법이 나와서 얼른 사용해봤습니다.~~

class Heap {
  #memory = []; //-- static으로 선언하면 장점이 있을까? Homework -> 21.10.05
  constructor () {
  }
  ...

  pop(){
    let node = this.#memory[0];
    ...
  }

  ...
}

이제 삽입과 추출 후에 정렬하는 함수를 추가해보겠습니다. MinHeap과 MaxHeap마다 정렬 기준이 다르기 때문에, 각각 class에서 재정의해주기로 합니다. 정렬하는 함수를 작성하다보니 부모 노드와 자식 노드에 접근할 일이 빈번하고, swap 하는 함수가 필요하여 해당 로직을 함수로 만들어보겠습니다. 추후에 추가된 private 개념 때문에라도 heap class에서 접근가능한 set/get이 필요했습니다.

class Heap {
  ...
  swap(idx1, idx2) {
    const temp = this.#memory[idx1];
    this.#memory[idx1] = this.#memory[idx2];
    this.#memory[idx2] = temp;
  }

  /* 부모와 자식간의 idx 관계는 문서에 게시된 링크에 있습니다.*/
  getParentIdx(idx) {
    return ~~((idx - 1) / 2); 
  }

  getLeftIdx(idx) {
    return idx * 2 + 1;
  }

  getRightIdx(idx) {
    return idx * 2 + 2;
  }

  /* 상속받은 class에서 memory 변수에 접근이 안되어 추가되었습니다. */
  getNode(idx) {
    return this.#memory[idx]; 
  }

  getParentNode(idx) {
    return this.#memory[this.getParentIdx(idx)];
  }

  getLeftNode(idx) {
    return this.#memory[this.getLeftIdx(idx)];
  }

  getRightNode(idx) {
    return this.#memory[this.getRightIdx(idx)];
  }

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

  size() {
    return this.#memory.length;
  }

  [util.inspect.custom]() {
    return this.#memory;
  }

  bubleUp(){ };
  bobleDown(){ };

  push(node) {
    ...
    this.bubleUp();
  }

  pop(){
    ...
    this.bubleDown();
    return node;
  }
  ...
}

class MaxHeap extends Heap {
  bubleUp() {
    let idx = this.size() - 1;
    while (
      this.getParentNode(idx) &&
      this.getParentNode(idx) < this.getNode(idx)
    ) {
        this.swap(idx, this.getParentIdx(idx));
        idx = this.getParentIdx(idx);
    }
  }

  bubleDown() {
    let idx = 0;
    
    while (
      this.getLeftNode(idx) !== undefined &&
      this.getLeftNode(idx) > this.getNode(idx) ||
      this.getRightNode(idx) > this.getNode(idx)
    ) {
      let largeIdx = this.getLeftIdx(idx);
      if (
        this.getRightNode(idx) !== undefined &&
        this.getRightNode(idx) > this.getNode(largeIdx)
      ) {
        largeIdx = this.getRightIdx(idx);
      }
      this.swap(idx, largeIdx);
      idx = largeIdx;
    }
  }
}

class MinHeap extends Heap {
  bubleUp() {
    let idx = this.size() - 1;
    
    while (
      this.getParentNode(idx) !== undefined &&
      this.getParentNode(idx) > this.getNode(idx)
    ) {
      this.swap(idx, this.getParentIdx(idx));
      idx = this.getParentIdx(idx);
    }
  }

  bubleDown() {
    let idx = 0;
    
    while (
      this.getLeftNode(idx) !== undefined &&
      this.getLeftNode(idx) < this.getNode(idx) ||
      this.getRightNode(idx) < this.getNode(idx)
    ) {
      let smallerIdx = this.getLeftIdx(idx);
      if (
        this.getRightNode(idx) !== undefined &&
        this.getRightNode(idx) < this.getNode(smallerIdx)
      ) {
        smallerIdx = this.getRightIdx(idx);
      }

      this.swap(idx, smallerIdx);
      idx = smallerIdx;
    }
  }
}

💡 Tip

만약 Node가 단순히 비교가 가능한 자료형이 아닌 객체라면 비교하는 로직을 comp 함수를 만들어서, 새로운 class에서 상속받아 오버라이팅하여 비교하도록 할 수 있습니다.

오늘은 이렇게 자료구조 heap에 대해 살펴보았습니다. 자료구조 Heap은 이진 트리를 기반으로 한 자료구조이고 부모 노드와 자식 노드간에는 대소 관계가 성립되지만, 형제간에는 대소관계가 정의되어 있지 않습니다. 우선순위 큐를 구현할 때 많이 쓰이며, 시간 복잡도가 O(logn)입니다. 사실 이미 훌륭한 자료구조 라이브러리들이 있습니다만, 오늘은 한번 직접 머리를 쥐어싸며 자료구조를 만들어보았습니다.