[Data Structure / JS] 이진 힙(Binary Heaps) / 우선순위 큐(Priority Queue)

힙(Heap)이란 ?

완전 이진트리 기반의 자료구조로, 최대 힙과, 최소 힙 두 종류로 구분됩니다. 최대 힙의 경우에는 루트노드에 가까울 수록 크고, 최소힙은 루트 노드에 가까울 수록 작은 값을 가집니다. 힙에서는 데이터의 중복이 허용되며, 주로 우선순위 큐를 구현하는데 사용됩니다. 나아가 힙 정렬, 다익스트라의 최단 경로 알고리즘에서도 사용됩니다.

 

힙은 부모자식간의 크기 차이만 비교합니다. 형제 노드 간에의 크기 차이를 고려하지 않습니다.

 

구현

힙은 일반적으로 각 요소에 효율적으로 접근할 수 있는 배열을 통해 구현됩니다. 인덱스 i에 위치한 노드의 부모는 (i-1)/2에 위치하며, 왼쪽 자식 노드는 2*i + 1, 오른쪽자식 노드는 2*i + 2에 위치하게 됩니다.

 

Heap에서의 삽입

 힙에서의 삽입은 새로운 요소의 힙을 가장 마지막 노드에 이어 추가한 뒤 해당 요소를 부모 요소와 비교해가며 힙의 특성에 맞게 재배치 합니다. 최대힙에서는 새롭게 삽입된 노드가 부모 노드보다 큰 경우 두 요소를 교환하고, 이러한 특성을 만족할 때 까지 반복합니다.

  insert(element) {
    this.values.push(element);
    this.bubbleUp();
  }
  
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

 

Heap에서의 삭제

 힙에서의 삭제는 root노드를 지운 후 새로운 root를 자식 요소와 비교하고 재배치하며 힙의 특성을 만족하도록 재배치합니다. root노드를 삭제하고 삭제된 root 노드의 자리에 힙의 마지막 요소를 옮깁니다. root 노드와 자식 노드들을 비교하며 최대힙의 경우 루트노드가 자식 노드들보다 작을때까지 자리 바꾸기를 반복합니다. 이때 자식 노드 중 더 큰 노드가 우선순위를 가집니다.

  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.bubbleDown();
    }
    return max;
  }
  
 bubbleDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }

 

Heap 전체 구현 코드

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }

  insert(element) {
    this.values.push(element);
    this.bubbleUp();
  }

  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.bubbleDown();
    }
    return max;
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  bubbleDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

 

우선순위 큐란?

큐는 먼저 들어오는 데이터가 먼저나가는 First In First Out 형식의 자료구조입니다. 우선순위큐는 데이터의 우선순위에 따라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조 입니다. 힙을 이용해 구현됩니다. 우선순위 큐는 배열이나 연결리스트를 통하여도 구현할 수 있는데, 배열이나 연결리스트로 구현할 경우 선형 자료구조이기 때문에 삽입 또는 삭제 연산이 O(n)의 시간복잡도를 가집니다. 반면 힙의 경우 완전 이진트리 구조이기 때문에 시간복잡도를 O(logN)까지 줄일 수 있습니다.

 

우선순위 큐 구현

기존 힙 구현에 Node를 생성하여 priority를 추가합니다. 그리고 priority를 중심으로 비교하여 노드들을 재배치 합니다.

아래는 힙을 약간 수정하여 구현한 우선순위 큐 코드입니다.

 

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

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

  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }

  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.bubbleDown();
    }
    return min;
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  bubbleDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.priority < element.priority) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild.priority < element.priority) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}