1ilsang

Developer who will be a Legend

자바스크립트로 힙(heap) 구현하기

2020-04-02 1ilsangJavaScript

기존에 힙 구현체가 자바라서 자바스크립트로도 구현해 보았다.

힙에 대한 설명은 이 링크에 정리되어 있다.

class Heap {
  constructor(size) {
    if (size && isNaN(size)) throw Error(`Invalidate param`);

    this.idx = 0;
    this.arr = new Array(size ? size : 11).fill(null);
  }

  add(n) {
    if (this.idx + 1 === this.arr.length) throw Error(`Stack overflow`);

    let idx = ++this.idx;
    this.arr[idx] = n;

    while (idx > 1) {
      const nextIdx = idx >> 1;
      const parent = this.arr[nextIdx];
      const cur = this.arr[idx];

      if (parent <= cur) break;

      this.arr[nextIdx] = cur;
      this.arr[idx] = parent;

      idx >>= 1;
    }

    return true;
  }

  print() {
    console.log(this.arr);
  }

  pop() {
    if (this.idx === 0) throw Error(`Empty stack`);

    const ret = this.arr[1];
    let idx = 1;

    this.arr[1] = this.arr[this.idx];
    this.arr[this.idx--] = null;

    while (idx < this.idx) {
      if (idx * 2 > this.idx || idx * 2 + 1 > this.idx) break;

      let nextIdx = idx * 2;
      if (this.arr[idx] <= this.arr[nextIdx]) nextIdx = idx;
      if (this.arr[nextIdx] > this.arr[idx * 2 + 1]) nextIdx = idx * 2 + 1;
      if (nextIdx === idx) break;

      const tmp = this.arr[idx];
      this.arr[idx] = this.arr[nextIdx];
      this.arr[nextIdx] = tmp;
      idx = nextIdx;
    }

    return ret;
  }

  peek() {
    return this.arr[this.idx];
  }
}

function main() {
  const heap = new Heap();
  for (let i = 10; i > 0; i--) {
    heap.add(i);
  }
  heap.print();
  while (heap.peek()) {
    console.log(heap.pop(), heap.idx);
    heap.print();
  }
}

main();
로그 보기
/**
 * 
[ null, 1, 2, 5, 4, 3, 9, 6, 10, 7, 8 ]

1 9
[ null, 2, 3, 5, 4, 8, 9, 6, 10, 7, null ]

2 8
[ null, 3, 4, 5, 7, 8, 9, 6, 10, null, null ]

3 7
[ null, 4, 7, 5, 10, 8, 9, 6, null, null, null ]

4 6
[ null, 5, 7, 6, 10, 8, 9, null, null, null, null ]

5 5
[ null, 6, 7, 9, 10, 8, null, null, null, null, null ]

6 4
[ null, 7, 8, 9, 10, null, null, null, null, null, null ]

7 3
[ null, 8, 10, 9, null, null, null, null, null, null, null ]

8 2
[ null, 9, 10, null, null, null, null, null, null, null, null ]

9 1
[ null, 10, null, null, null, null, null, null, null, null, null ]

10 0
[ null, null, null, null, null, null, null, null, null, null, null ]
 */

그럼 이만!