[자료구조] Heap (힙)

1. 정의 

힙은 최댓값 최소값을 빠르게 찾아내기 위해 고안된 '완전이진트리' 자료구조다.


* CS 변수 저장 공간

 

 

2. 효용성

최대/최소를 검색하는데 O(1)의 시간봅잡도를 가진다. 

3. 연산

Push

1. 트리의 마지막 노드에 값을 넣는다.
2. 부모 노드와 값을 비교한다.
3. 루트에 도달하거나, 부모 노드보다 값이 작다면(최대힙기준) break 한다.
4. 부모 노드보다 값이 크다면 부모 노드와 swap 한다.
5. 재귀적으로 다시 부모 노드와 비교한다.(2번부터 다시 시작)
   
   

Pop

1. 트리의 루트값을 저장한다.(return 용)
2. 트리의 마지막 노드를 루트로 올린다.
3. 왼쪽 자식노드, 오른쪽 자식노드, 자신 3개의 값을 비교한다.
4. 자신이 가장 크다면(최대힙기준) break 한다.
5. 아니라면 가장 큰 값과 swap 한다.
6. 재귀적으로 다시 왼쪽, 오른쪽 자식노드와 비교한다.(3번부터 다시 시작)

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();