1. Binary Heap

Binary Heap(이하 BH)은 BST보다 간단하다. MAX인지 MIN인지에 따라서 부모가 자식보다 크냐 아님 작으냐로 구분하기만 하면 된다. 형제노드사이의 관계는 전혀 없다. 그냥 부모보다 작으면 된다. 그럼 영어로 설명을 적어보겠다.

Binary heap

-- Very similar to a binary search tree, but with some different rules!

• In a MaxBinaryHeap the parent is greater than the children, but there are no guarantees between sibling nodes.

• A binary heap is as compact as possible. All the children of each node are as full as they can be and left children are filled out first.

-- In a MaxBinaryHeap, parent nodes are always larger than child nodes. In a MinBinaryHeap, parent nodes are always smaller than child nodes.

-- We fill them out from left to right so we don’t end up with these unbalanced wonky one sided trees. like the worst case for BST

-- With a little bit of math, we can represent heaps using arrays! It’s easier to do that.

MaxBinaryHeap

• It can flatten the heap into array. Array representation of binary heap
• For any index of an array n.. The left child is stored at 2n+1. The right child is at 2n+2
• For any child node at index n… Its parent is at index Math.floor((n-1)/2))

Binary Heap은 부모보다 작기만 하면 되기 때문에 몇가지 특징이 있다. 바로 array로 나타낼 수 있다는 점이다.

max = [10,8,9,4,5,7,8] 요렇게 말이다. MaxBH라고 할때 ARR안에 있는 것을 그대로 BFS방식으로 나열하면 BH tree가 형성된다.(마치 DFS preOrder과 같다) 이때 부모와 자식이 어디에 위치해 있는지 수식으로 나타낼 수 있다. 위에 처럼. 그럼 Max BH Insert를 살펴보자.

1-1. Max Binary Heap Insert

우선 root를 간단하게 arr 로 나타내자. 그럼 로직을 알아보자!

Insert pseudocode

-- Push the value into the values property on the heap
-- Bubble the value up to its correct spot!

complex Insert pseudocode

-- Push the value into the values property on the heap

-- Bubble up:

• Create a variable called Index which is the length of the values property -1
• Create a variable called parentIndex which is the floor of (index-1)/2

-- Keep looping as long as the values element at the parentIndex is less than the values element at the child index

• Swap the value of the values element at the parentIndex with the value of the element property at the child index

• Set the index to be the parentIndex, and start over!

일단 node를 제일 끝에다가 추가해준다. 제일 끝에다가 추가하면 tree 그림상으로는 제일 왼쪽노드 밑에 달리게 된다. 그럼 그 노드가 parentNode랑 비교했을때 크면 swap하고 아니면 그자리에 있게 된다.

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  // ex) [100, 83, 73, 56, 70, 64, 49]

        100
      83   73
   56  70 64  49
 new

  insert(num) {
    this.values.push(num);

    function swap(arr, parentIdx, childIdx) {
      var temp = arr[childIdx];
      arr[childIdx] = arr[parentIdx];
      arr[parentIdx] = temp;
    }

    var childIndex = this.values.length - 1;
    var parentIndex = Math.floor((childIndex - 1) / 2);

    // if child is greater than parent, then we have to swap.
    while (this.values[childIndex] > this.values[parentIndex]) {
      swap(this.values, parentIndex, childIndex);
      childIndex = parentIndex;
      //while 밖에 parentIndex 가 있기 때문에 parentIndex를 갱신하려면 while안에 넣어줘야한다.
      parentIndex = Math.floor((childIndex - 1) / 2);
    }

    console.log(childIndex, parentIndex);
    return this.values;
  }
}

그럼 Max BH에서 가장 큰 수를 뽑아내고 TREE를 다시 정렬하는 법을 알아보자.

1-2. Max Binary Heap ExtractMax

로직을 알아보자.

ExtractMax(remove) pseudocode

-- Swap the first value in the values property with the last one.
-- Pop from the values property , so you can retrun the value at the end.
-- Have the new root ‘sink down’ to the correct spot.

• Your parent index starts at 0 (the root).
• Find the index of the left child: 2*index + 1 (make sure it’s not out of bounds).
• Find the index of the right child: 2*index + 2 (make sure it’s not out of bounds).
• If the left or right child is greater than the element …swap. If both left and right children are larger, swap with the largest child.
• The child index you swapped to now becomes the new parent index.
• Keep looping and swapping until neither child is larger than the element.
• Return the old root!

이번엔 insert랑 반대로 간다. Max와 가장 끝에 있는 node를 swap한다음에 max를 뽑아내고 root자리에 있는 node가 sink down을 시작한다. children중에 큰 수가 있는지 확인하고 있으면 swap 없으면 stay 한다.

extractMax() {
  if (!this.values.length) return;

  function swap(arr, parentIdx, childIdx) {
    var temp = arr[parentIdx];
    arr[parentIdx] = arr[childIdx];
    arr[childIdx] = temp;
  }

  swap(this.values, 0, this.values.length - 1);
  var oldRoot = this.values.pop();

  var pi = 0;

  while (true) {
    var parent = this.values[pi];
    var length = this.values.length;
    var leftIdx = 2 * pi + 1;
    var rightIdx = 2 * pi + 2;
    var left = this.values[leftIdx];
    var right = this.values[rightIdx];

    var swapIdx = null;

    if (leftIdx < length) {
      if (left > parent) {
        swapIdx = leftIdx;
      }
    }

    if (rightIdx < length) {
      if (
        // right > left .. keep it in mind
        (swapIdx && right > left) ||
        (swapIdx === null && right > parent)
      ) {
        swapIdx = rightIdx;
      }
    }

    if (swapIdx === null) break;

    swap(this.values, pi, swapIdx);
    pi = swapIdx;
  }
  return oldRoot;
}

swapIdx 변수를 사용한 점이 인상깊다. swap이 될만하면 swapIdx에는 무언가가 담길것이고 그게 아니면 바로 break 된다.

그럼 다음으로 Priority Queue에 대해서 알아보자!