1. Priority Queue

BH를 이용해서 우선순위를 정하고 가장 급한것을 먼저 처리하는 프로그램을 의미한다. 일단 상황을 정하자. 지금 우리는 응급실(ER)에 와있다. 환자별로 증상과 응급정도를 표시해서 분류한다음 가장 급한사람이 먼저 치료받도록 해야한다고 하자. 이때 응급정도의 숫자가 낮을 수록 긴급한거라고 하면 MIN BH를 써야한다.

또한 가장 작은 숫자가 가장 먼저 빠져나가야 하므로 queue를 사용한다.

1-1. Priority Queue Insert

앞서 MAX와 반대로 로직을 적어주면 되고 pri를 비교해야한다.

class Node {
  constructor(val, pri) {
    this.val = val;
    this.pri = pri;
  }
}

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  // this 를 넘겨야 해서 이렇게 한다
  swap(parentIdx, childIdx) {
    var temp = this.heap[parentIdx];
    this.heap[parentIdx] = this.heap[childIdx];
    this.heap[childIdx] = temp;
  }

  enqueue(val, pri) {
    var newNode = new Node(val, pri);
    this.heap.push(newNode);
    if (this.heap.length > 1) this.enqueueHelp();
    return this.heap;
  }

  enqueueHelp() {
    var childIdx = this.heap.length - 1;
    var parentIdx = Math.floor((childIdx - 1) / 2);
    console.log(parentIdx);

    // if child is less than parent, then we have to swap.
    while (this.heap[childIdx].pri < this.heap[parentIdx].pri) {
      this.swap(parentIdx, childIdx);
      childIdx = parentIdx;
      if (childIdx < 1) break;
      parentIdx = Math.floor((childIdx - 1) / 2);
    }
  }
}

var ER = new PriorityQueue();
ER.enqueue("flu", 5);
ER.enqueue("corona", 3);
ER.enqueue("heart Attack", 1);
ER.enqueue("scratch", 7);
ER.enqueue("hungry", 9);

dequeue도 마찬가지로 반대로 적어주고 pri를 비교해주면 된다. 그럼 hash table에 대해서 알아보자