[algorithm] Max Heap 구현하기

프로그래머스 기준 레벨이 3 정도 되면, Heap을 사용해야 하는 일이 생긴다. 하지만, 다른 언어와 달리 JavaScript에는 MaxHeap이 없기 때문에 직접 구현을 해서 사용해야 한다.

하나 만들어 둔 후, 문제를 풀 때 갖다 쓰면 편하다.

배열의 index를 조정해 이진 트리 구조로 사용하였다. 자식 노드는 부모 노드의 2배만큼의 index를 갖는다.
계산을 쉽게 해주기 위해 0번 index에는 가장 큰 수를 할당하여 채워주었고, 실제로는 1 index부터 시작한다.

constructor() {

    this.heap = [];

    this.heap.push(1e9);

  }

 

값을 추가(insert)하면 일단, 배열에 값을 넣어준 후, upheap을 해준다.
upheap은 가장 마지막의 숫자가 자신의 부모보다 크다면 계속 위로 올라가는 방식으로, 현재 넣은 값이 가장 클 경우, 루트(1 index)까지 올라갈 수 있다.

insert(val) {

    this.heap.push(val);

    this.upheap(this.heap.length - 1);

  }

  upheap(pos) {

    let tmp = this.heap[pos];

    while (tmp > this.heap[Math.floor(pos / 2)]) {

      this.heap[pos] = this.heap[Math.floor(pos / 2)];

      pos = Math.floor(pos / 2);

    }

    this.heap[pos] = tmp;

  }

 

반대로 최대값을 뺀다면(get), 배열에서 가장 앞에 위치한 index 1의 수를 가져온 후, downheap을 해준다.
downheap은 루트 값이 빠진 위치에 가장 마지막 수를 넣어준 후, 자식 노드들과 비교하여 큰 값을 위로 올려준다. 이 과정을 반복하면 루트에 넣어준 마지막 숫자가 내려가고, 큰 수가 위로 올라가도록 정렬된다.

get() {

    if (this.heap.length === 2) return this.heap.pop();

    if (this.heap.length === 1) return false;

    let res = this.heap[1];

    this.heap[1] = this.heap.pop();

    this.downheap(1, this.heap.length - 1);

    return res;

  }

  downheap(pos, len) {

    let tmp = this.heap[pos], child;

    while (pos <= Math.floor(len / 2)) {

      child = pos * 2;

      if (this.heap[child] < this.heap[child + 1]) child++;

      if (tmp >= this.heap[child]) break;

      this.heap[pos] = this.heap[child];

      pos = child;

    }

    this.heap[pos] = tmp;

  }

 

추가적으로 size를 구하거나 가장 큰 수를 꺼내지 않고 확인할 수 있는 top 같은 메서드도 추가할 수 있다.

 

class maxHeap {

  constructor() {

    this.heap = [];

    this.heap.push(1e9);

  }

 

  insert(val) {

    this.heap.push(val);

    this.upheap(this.heap.length - 1);

  }

 

  upheap(pos) {

    let tmp = this.heap[pos];

    while (tmp > this.heap[Math.floor(pos / 2)]) {

      this.heap[pos] = this.heap[Math.floor(pos / 2)];

      pos = Math.floor(pos / 2);

    }

    this.heap[pos] = tmp;

  }

 

  get() {

    if (this.heap.length === 2) return this.heap.pop();

    if (this.heap.length === 1) return false;

    let res = this.heap[1];

    this.heap[1] = this.heap.pop();

    this.downheap(1, this.heap.length - 1);

    return res;

  }

 

  downheap(pos, len) {

    let tmp = this.heap[pos], child;

    while (pos <= Math.floor(len / 2)) {

      child = pos * 2;

      if (this.heap[child] < this.heap[child + 1]) child++;

      if (tmp >= this.heap[child]) break;

      this.heap[pos] = this.heap[child];

      pos = child;

    }

    this.heap[pos] = tmp;

  }

  size() {

    return this.heap.length - 1;

  }

 

  top() {

    return this.heap[1];

  }

}