Binary Heaps with JS

• 단일 연결 리스트
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회 (bfs,dfs)
• 이진 힙 
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

---

Binary Heaps

힙은 트리 구조의 일종이다. 이진 탐색트리와 비슷하지만 다른 규칙을 가지고 있다. 

최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다.

힙은 왼쪽과 오른쪽 노드에 순서가 없다. (단지 부모 노드만 자식 노드보다 큰 값을 가진다.)

(왼) 이진 힙, (오) 이진 트리

---

이진 힙의 원리 

부모에서 자식으로 가기 위해서는 부모에 2를 곱하고 left일 경우 +1, right일 경우 +2로 이동을 한다.

반대로 자식에서 부모를 갈 때는 (자식-1)/2를 해서(나머지는 생략) 이동하면 된다.

 

insert

insert의 시작은 일단 트리의 맨 뒤에 저장을 하고 시작한다. 

배열에 일단 값이 들어오면 push를 한 후 부모와 비교해서 교체해준다.

교체를 할 때는 기존의 idx 값을 부모의 idx로 바꿔준다. 

while의 조건은 idx > 0 일 때 작동할 수 있게 설정한다. 

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  insert(value) {
    this.values.push(value);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];

    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(50);
console.log(heap);

//[50, 41, 39, 33, 18, 27, 12]

---

delete

 

extractMax() 는 최대 이진 힙에서 가장 큰 값을 추출하는 메서드로 설정한다. 

1. 최대값을 추출하기 위해 먼저 힙의 루트에 있는 값을 가져온다. 최대 이진 힙에서 루트에 있는 값은 최댓값이다.
2. 힙에서 값이 추출되면, 힙의 마지막 노드를 루트로 이동시킨다. (힙의 구조를 유지하기 위한 작업)
3. 루트로 이동된 마지막 노드를 기준으로 sink down() 작업을 수행한다. 이 작업은 힙의 조건을 만족하도록 노드를 아래로 이동시킨다. 루트에서부터 시작하여 자식 노드 중에서 더 큰 값과 교환하면서 아래로 내려간다.

이 과정을 거치면 힙의 최댓값이 추출되고, 추출된 값은 반환시킨다. 

  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
  }

sinkDown() 은 최대 이진 힙에서 루트 노드를 아래로 이동시켜 힙 속성을 복원하는 역할을 한다.

 주어진 인덱스부터 시작하여 아래로 내려가면서 자식 노드와 비교하여 필요에 따라 값을 교환한다.

1. 인덱스 0 에서 시작한다. (힙의 루트를 가리키는 위치)
2. 주어진 인덱스를 기준으로 왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 미리 계산한다.
3. 왼쪽 자식 노드의 값과 오른쪽 자식의 노드의 값을 비교하여 더 큰 값을 swap변수에 기억한다. (swap은 더 큰 자식 노드의 인덱스를 의미)
4. 현재 노드가 자식 노드보다 크다면(즉, 최대 힙의 조건을 만족한다면) 교환이 필요하지 않으므로 반복문을 종료
5. 그렇지 않으면, 현재 노드와 swap된 자식 노드의 값을 교환하고, 현재 인덱스를 swap된 자식 노드의 인덱스로 업데이트
6. 이 과정을 반복하여 현재 노드가 더 이상 자식 노드보다 크지 않거나 더 이상 자식 노드가 없을 때까지 반복

  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }

---

전체 코드 

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  insert(element) {
    this.values.push(element);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
  }
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);

console.log(heap);
// 55, 39, 41, 18, 27, 12, 33
heap.extractMax();
//41,39,33,18,27,12

console.log(heap);