우선순위 큐, 힙

우선순위 큐에 대하여 알아보고 힙 자료구조를 통하여
JS 코드로 어떻게 짜는지에 대하여 알아보자.

 

🧲 우선순위 큐란?

• 일반 FIFO인 큐와 다르게 우선순위가 높은 노드 먼저 나갈 수 있다.
• 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 사용한다

 

🧲 구현

1. 배열 및 연결리스트로 구현
   간단히 구현이 가능한 장점이 있지만 데이터를 삭제 및 삽입해야할 경우 모든 인덱스를 탐색하는 과정이 있기 때문에 시간복잡도가 O(N)이 되므로 상대적으로 성능이 부족하다
2. 힙으로 구현
   구현이 어렵지만 enqueue, dequeue 시간 복잡도가 O(logN)이다
   단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 힙 정렬과 동일하며 이 경우엔 O(NlogN)이다.

 

🧲 구현 방법에 따른 시간 복잡도

 

🧲 힙이란

O(NlogN) 대표적으로 heap이 있다.

heap은 이진트리 형태로 데이터를 정렬하여 사용하는 자료구조로써,
수시로 변동되는 데이터에서, 최댓값, 최솟값을 빠르게 찾아주도록 도와주는 자료구조이다.

 

🧲 힙의 특징

• 완전 이진 트리 자료구조이다.
  완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 모두 채워져있으며, 마지막 레벨의 모든 노드는 왼쪽부터 오른쪽으로 차있다.
  즉 루트 노드로부터 시작하여 왼쪽에서 오른쪽 자식 노드 순서대로 데이터가 순차적으로 삽입되는 트리를 의미한다.
• 최소힙
  루트 노드가 가장 작은 값을 가지며 값이 작은 데이터가 우선적으로 제거된다.
  부모노드가 항상 자식노드보다 값이 작다.
• 최대힙
  루트 노드가 가장 큰 값을 가지며 값이 큰 데이터가 우선적으로 제거된다.
  부모노드가 항상 자식노드보다 값이 크다.
• 힙의 인덱스 관계
  좌측 자식 노드의 인덱스 : (부모 노드의 인덱스 2 ) + 1
  우측 자식 노드의 인덱스 : (부모 노드의 인덱스 2 ) + 2
  부모 노드의 인덱스 : Math.floor( 자식노드의 인덱스 - 1 / 2 )
• 배열을 힙으로 구현하면 arr[0]이 최상단 부모이다
• N개의 데이터를 힙 구조로 만드는 복잡도는 O(NlogN)이다

 

---

🧲 Min Heap 구현하기

class MinHeap {
  constructor() {
    this.arr = [];
  }

  getLeftChildIndex = (currIndex) => currIndex * 2 + 1;
  getRightChildIndex = (currIndex) => currIndex * 2 + 2;
  getParentIndex = (currIndex) => Math.floor((currIndex-1) / 2);
}

 

🧲 insert, heapifyUp

 

1. 배열의 끝에 넣는다

2. MinHeap형태를 갖출 수 있도록 heapifyUp를 통해 아래에서 위로 이동하며 새로 삽입한 노드의 제자리를 찾아준다.

 

Min Heap의 heapifyUp메서드 

1. 먼저 새로운 노드의 부모노드를 찾는다
2. 부모와 새로운 노드의 값을 비교한다
3. 만약 부모보다 새로운 노드가 작으면 이 둘을 swap한다
4. 새로운 노드가 루트노드가 될때까지 3을 반복한다

class MinHeap {
  // ....
  insert(value) {
    this.arr.push(value); // 배열 마지막에 새로운 값 추가
    this.heapifyUp(this.arr.length - 1); // 아래에서 위로 힙 정리하기
  }

  heapifyUp(index) {
    if (index) {
      const parentIndex = this.getParentIndex(index);

      // 부모값이 새로 삽입된 값보다 크면 부모의 자리를 아래로 내린다
      if (this.arr[parentIndex] > this.arr[index]) {
        const temp = this.arr[parentIndex];
        this.arr[parentIndex] = this.arr[index];
        this.arr[index] = temp;
        this.heapifyUp(parentIndex);
      }
    }
  }
}

 

---

🧲 remove, heapifyDown

1. 배열의 길이가 0이면 false를 리턴한다
2. 길이가 1이상이면 최상위 노드를 제거하고 마지막 노드를 최상위 노드로 교체한다
3. MinHeap형태를 갖출 수 있도록 heapifyDown를 통해 위에서 아래로 이동하며 2번에서 만든 새로운 최상위 노드의 제위치를 찾는다

 

Min Heap의 heapifyDown메서드 

1. 왼쪽, 오른쪽 자식 노드를 찾는다
2. 왼쪽과 오른쪽 중 작은 노드를 최상위 노드와 비교한다.
3. 최상위노드가 더 크면 이 둘을 swap한다.
4. 왼쪽 자식이 노드가 없을 때까지 (= leaf노드)  1~3을 반복한다.

class MinHeap {
  // ....
  remove() {
    if (this.arr.length === 0) {
      return false;
    }
    const removed = this.arr[0];
    this.arr[0] = this.arr.pop(); // 마지막 노드를 최상위노드로 올린다.
    this.heapifyDown(0);
  }

  heapifyDown(index) {
    // 왼쪽자식노드가 없으면 잎노드이므로 리턴
    if (this.getLeftChildIndex(index) >= this.arr.length) {
      return;
    }
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    // 왼쪽, 오른쪽 자식 중 더 작은 자식을 찾는다.
    let smallerChildIndex = leftChildIndex;
    // 오른쪽 자식이 더 작을시
    if (this.arr[leftChildIndex] > this.arr[rightChildIndex]) {
      smallerChildIndex = rightChildIndex;
    }

    if (this.arr[index] > this.arr[smallerChildIndex]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[smallerChildIndex];
      this.arr[smallerChildIndex] = temp;
      this.heapifyDown(smallerChildIndex);
    }
  }
}

 

🧲 전체코드

class MinHeap {
  constructor() {
    this.arr = [];
  }

  getLeftChildIndex = (currIndex) => currIndex * 2 + 1;
  getRightChildIndex = (currIndex) => currIndex * 2 + 2;
  getParentIndex = (currIndex) => Math.floor((currIndex - 1) / 2);

  insert(value) {
    this.arr.push(value); // 배열 마지막에 새로운 값 추가
    this.heapifyUp(this.arr.length - 1); // 아래에서 위로 힙 정리하기
  }

  heapifyUp(index) {
  	// 최상단이 아닌 경우
    if (index > 0) {
      const parentIndex = this.getParentIndex(index);

      // 부모값이 새로 삽입된 값보다 크면 부모의 자리를 아래로 내린다
      if (this.arr[parentIndex] > this.arr[index]) {
      	// swap
        const temp = this.arr[parentIndex];
        this.arr[parentIndex] = this.arr[index];
        this.arr[index] = temp;
        // 계속heapify
        this.heapifyUp(parentIndex);
      }
    }
  }

  remove() {
    if (this.arr.length === 0) {
      return false;
    }
    const removed = this.arr[0];
    this.arr[0] = this.arr.pop(); // 마지막 노드를 최상위노드로 올린다.
    this.heapifyDown(0);
  }

  heapifyDown(index) {
    // 왼쪽자식노드가 없으면 잎노드이므로 리턴
    if (this.getLeftChildIndex(index) >= this.arr.length) {
      return;
    }
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    // 왼쪽, 오른쪽 자식 중 더 작은 자식을 찾는다.
    let smallerChildIndex = leftChildIndex;
    // 오른쪽 자식이 더 작을시
    if (this.arr[leftChildIndex] > this.arr[rightChildIndex]) {
      smallerChildIndex = rightChildIndex;
    }

    if (this.arr[index] > this.arr[smallerChildIndex]) {
      // swap
      const temp = this.arr[index];
      this.arr[index] = this.arr[smallerChildIndex];
      this.arr[smallerChildIndex] = temp;
      // 계속 heapifyup
      this.heapifyDown(smallerChildIndex);
    }
  }
}

const heap = new MinHeap();

heap.insert(5);
heap.insert(3);
heap.insert(1);
heap.insert(4);
heap.insert(0);
console.log(heap.arr); // [ 0, 1, 3, 5, 4 ]
heap.remove();
console.log(heap.arr); // [ 1, 4, 3, 5 ]