코딩테스트를 위한 PriorityQueue

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 흔하디 흔한 우선순위큐는 내장되어있지 않다. 따라서, 우리는 우선수위큐를 "직접" 만들어야한다. 우선순위큐에 대해 알아보자

우선순위 큐

생성자

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

• heap 배열을 초기화하는 생성자다.

삽입 enqueue

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }

• heap 배열에 value를 push하고 힙정렬을 진행한다.

삭제 dequeue

dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
}

• 삭제하려는 값은 맨위의 최소값이므로 (현재 코드는 최소힙을 기준으로 작성) 0번째 인덱스와 마지막인덱스를 교환한다.
• 다시 힙정렬을 진행한다.

heapifyUp() 위쪽으로 재정렬

_heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
       //우선순위큐는 이진트리를 기반으로 하기때문에 
       //parentIndex 는 자식 노드의 인덱스에 절반과 비슷하다.
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];
        //부모보다 크기때문에 최소힙 성립
      if(element >= parent) break;
        //그렇지 않으면 부모와 자리바꾸기
      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
 }

• 값을 삽입하면 오름차순으로 정렬해야한다. (삽입한 값이 맨뒤에 있다.)
• 삽입된 위치(index) 값부터 (heap 배열에 push 했으므로 맨끝값) 부모 노드를 탐색하면서 바꿀 값을 찾는다.

heapifyDown() 아래쪽으로 재정렬

_heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
    //자식 인덱스를 확인
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;
    //왼쪽자식부터 부모가 더 크다면 바꿔야할 인덱스로 판명
      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }
    //오른쪽자식
      if(rightChildIndex < length){
      //왼쪽을 안바꿔도되고(null), 오른쪽 자식의 값이 부모보다 작다면 바꿔야한다.
      //왼쪽을 바꿔도되고, 오른쪽 자식의 왼쪽 자식의 값보다 작다면 오른쪽 자식을 바꿔야한다.
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

    //바꿀게없다면 패스
      if(swapIndex === null) break;
    //부모와 자식을 바꾼다.
      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }

• dequeue 를 하게 되면 맨위에 값이 최대값으로 바뀌기 때문에 자식을 탐색하면서 정렬해야한다.

전체 코드

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

  enqueue(value){
    this.heap.push(value);
    this._heapifyUp();
  }

  dequeue(){
    const min = this.heap[0];
    const end = this.heap.pop();

    if(this.heap.length > 0){
      this.heap[0] = end;
      this._heapifyDown();
    }

    return min;
  }

  _heapifyUp() {
    let index = this.heap.length -1;
    const element = this.heap[index];

    while(index > 0){
      const parentIndex = Math.floor((index - 1) /2 );
      const parent = this.heap[parentIndex];

      if(element >= parent) break;

      this.heap[index] = parent;
      index = parentIndex;
    }
    this.heap[index] = element;
  }

  _heapifyDown(){
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while(true){
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;

      if(leftChildIndex < length){
        if(this.heap[leftChildIndex] < element){
          swapIndex = leftChildIndex;
        }
      }

      if(rightChildIndex < length){
        if(
          (swapIndex === null && this.heap[rightChildIndex] < element) ||
          (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
        ){
          swapIndex = rightChildIndex;
        }
      }

      if(swapIndex === null) break;

      this.heap[index] = this.heap[swapIndex];
      index = swapIndex;
    }

    this.heap[index] = element;
  }
}