이진 힙(Binary Heap), 자바스크립트로 구현하기

✓ 힙 (Heap)

 

힙이란 트리 기반 자료구조로 힙 속성을 만족하는 거의 완전한 트리이다. 힙 속성이란 예를 들어, 최대힙의 경우 부모 노드는 반드시 자식 노드보다 커야 한다는 법칙이다. 따라서 최상위 노드는 최대값을 가지게 된다. 따라서 최상위 노드는 최대값을 가지게 된다. 이러한 힙의 특성으로 힙은 우선수위 큐를 구현하는데 적합한 자료구조이다. 힙은 부모와 자식 노드 간의 관계만이 정의되어 있을 뿐, 현제 또는 사촌 노드 간의 우선수위는 정해진 것이 없다.

 

 

✓ 이진 힙 (Binary Heap)

 

이진 힙은 힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태인 힙이다. 이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다. 이진 힙은 완전 이진 트리라는 조건을 만족해야한다. 모든 레벨의 노드가 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 차 있어야 한다. 이진 힙은 부모 노드 값이 자식 노드 값보다 크냐 작냐에 따라 최대 힙, 최소 힙으로 나뉜다.

 

 

 

트리를 T, 임의 내부노드를 v 라고 하면 다음과 같다.

 

1. 뿌리노드를 제외한 각 내부노드는 key(T.parent(v)) < key(v) 또는 key(T.parent(v)) > key(v) 이다. 즉, 키 값은 오름차순이거나 내림차순이다.

2. 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다.

 

 

✓ 코드로 구현하기

 

function swap(idx1, idx2, arr) {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

function getParentIdx(idx) {
  return Math.floor((idx - 1) / 2);
}

function insert(heap, item) {
  heap.push(item);
  let curIdx = heap.length - 1;
  let pIdx = getParentIdx(curIdx);
  while (pIdx >= 0 && heap[curIdx] > heap[pIdx]) {
    swap(curIdx, pIdx, heap);
    curIdx = pIdx;
    pIdx = getParentIdx(curIdx);
  }
  return heap;
}

const binaryHeap = function (arr) {
  return arr.reduce((heap, item) => {
    return insert(heap, item);
  }, []);
};

 

 

💻 Math.floor()

: 주어진 숫자와 같거나 작은 작은 정수 중에서 가장 큰수를 반환한다.

console.log(Math.floor(5.95));
// expected output: 5

console.log(Math.floor(5.05));
// expected output: 5

console.log(Math.floor(5));
// expected output: 5

console.log(Math.floor(-5.05));
// expected output: -6