우선순위 큐(Priority Queue), 힙(Heap)

→ Open in Slid

• 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.

* 해당 자료는 '동빈나'님의 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약 영상을 토대로 정리한 내용임을 밝힙니다.

https://www.youtube.com/watch?v=AjFlp951nz0

* 또한 코드로 구현한 부분은 https://velog.io/@ssh1997/JavaScript-%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%9C-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue 해당 블로그를 참조했음을 밝힙니다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.

ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우

구현방법

1. 리스트
2. 힙(Heap)

시간복잡도 (구현방법에 따라)

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)

• 이 경우 시간 복잡도는 O(NlogN)입니다.

힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조의 일종입니다.
• 힙에서는 항상 루트 노드(root node)를 제거합니다.
• 최소 힙(min heap)
  1. 루트 노드가 가장 작은 값을 가집니다.
  2. 따라서 값이 작은 데이터가 우선적으로 제거됩니다.
• 최대 힙(max heap)
  1. 루트 노드가 가장 큰 값을 가집니다.
  2. 따라서 값이 큰 데이터가 우선적으로 제거됩니다.

<최소 힙의 예시>

완전 이진 트리 (Complete Binary Tree)

루트(root) 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미합니다.

최소 힙 구성 함수: Min-Heapify()

(상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체합니다.

힙에 새로운 원소가 삽입될 때 (enQueue())

힙에서 원소가 제거될 때 (deQueue())

1. 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다.

2. 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) swap()를 진행합니다.

class Queue {
    data = [];
    // firstIndex = 0;
  
    enQueue = (data) => {
      this.data.push(data);
    };
  
    deQueue = () => {
      return this.data.shift();
      // 이 부분이 O(n) 의 시간이 걸리는게 문제일수도 있어서
      // 맴버변수로 firstIndex를 저장하며
      // return this.data[firstIndex++]; 로 대체할 수 도 있겠다.
    };
  }

• enQueue( data ) 를 통해 data 를 삽입할 수 있다.
• deQueue( ) 를 통해 첫번째 데이터를 추출할 수 있다.

다음으로 이를 상속받아 메소드들을 선언해 보았다.

class PriorityQueue extends Queue {
  enQueue = () => {};

  deQueue = () => {};
}

구현 - enQueue()

다음으로 재귀적으로 수행할 메소드와 swap 메소드를 선언해 주었다.

인자로는 비교할 데이터와 인덱스를 주어 부모노드의 값에도 접근할 수 있게 했다.

class PriorityQueue extends Queue {
  swap = (a, b) => {
    const temp = this.data[a];
    this.data[a] = this.data[b];
    this.data[b] = temp;
  };

  compareBottomUp = (data, index) => { // 상향식 우선순위 비교
    const parentIndex = Math.floor((index - 1) / 2); // 나머지 버림으로 부모 노드 index 유추
    if (this.data[parentIndex] < data) {
      this.swap(index, parentIndex);
      this.compareBottomUp(data, parentIndex);
    }
  };

  enQueue = (data) => {
    this.data.push(data);
    this.compareBottomUp(data, this.data.length - 1);
  };
}

const priorityQueue = new PriorityQueue();

priorityQueue.enQueue(1);
priorityQueue.enQueue(2);
priorityQueue.enQueue(3);

console.log(priorityQueue.data);
// output : [3, 1, 2]

결과

구현 - deQueue ( )

class PriorityQueue extends Queue {
  :
  :

  compareTopDown = (data, index) => { // 하향식 우선순위 비교
    const childIndexBase = index * 2;
    let target = childIndexBase + 1;
    if (this.data[childIndexBase + 1] < this.data[childIndexBase + 2]) {
      target += 1;
    } // 좌, 우 자식 노드 중 큰 노드를 선택
    if (this.data[target] > data) {
      this.swap(target, index);
      this.compareTopDown(data, target);
    }
  };

  deQueue = () => {
    const result = this.data[0];
    const data = this.data.pop();
    this.data[0] = data; // shift() 는 O(n) 이므로 마지막 노드를 pop( ) 하여 치환
    this.compareTopDown(data, 0);
    return result;
  };
}

const priorityQueue = new PriorityQueue();

priorityQueue.enQueue(1);
priorityQueue.enQueue(2);
priorityQueue.enQueue(3);
priorityQueue.enQueue(4);
priorityQueue.enQueue(3);
priorityQueue.enQueue(1);

console.log(priorityQueue.deQueue());
// output : 4

console.log(priorityQueue.data);
// output : [3, 3, 2, 1, 1]