[알고리즘] 이진 힙과 우선순위 큐 (자바스크립트)

이진 힙 (Binary Heap)

기본적으로 힙은 트리 구조의 한 종류이다. 이진 힙 외에도 굉장히 많은 힙 알고리즘이 존재한다. 이진 힙은 최대 힙, 최소 힙으로 구분할 수 있다. 힙 구조는 그래프 순회를 위한 우선순위 큐 (Priority Queue) 구현에 주로 사용된다.

 

최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 루트부터 노드를 타고 내려갈수록 더 작은 값을 갖는다는 뜻이다. 최소 이진 힙에서는 그 반대로, 부모 노드가 언제나 좌우의 자식 노드보다 작은 값을 갖는다. 오름차순, 내림차순으로 생각해도 될 듯

 

그럼 이진 탐색 트리(BST)와 비슷한 것 아닌가? 할 수 있곘지만, 이진 탐색 트리와 다르게 좌우 자식 노드의 크기 순서를 고려하지 않는다.

 

힙 정렬

트리 구조를 갖는 힙을 Flatten한 배열로 변환할 수 있다. 루트부터 시작하여 각 원소는 인덱스를 갖는다. 이를 통해 규칙을 발견할 수 있었는데, 배열 내부 모든 노드 인덱스에 n에 대해 왼쪽 자식은 2n+1, 오른쪽 자식은 2n+2에 위치한다는 점이다. 따라서 부모의 위치를 기반으로 자식을 찾을 수 있게 된다. 역으로 자식 노드의 인덱스를 통해 해당 자식 노드의 부모 노드 인덱스를 파악할 수도 있다. 자식 노드 인덱스 n 기준 floor((n-1)/2) 위치에 부모 노드가 존재한다.

 

클래스 셋업 : MaxBinaryHeap

먼저 최대 이진 힙의 기본 클래스를 셋업해보자. 최소 이진 힙 또한 굉장히 유사하기 때문에 한 번만 구현한다. value = [] 프로퍼티가 클래스의 구성요소 전부이다. 수많은 노드를 만들어 하나하나 직접 연결하는 대신, 그냥 배열에 저장해 위치 기반으로 구조를 모형화하는 방식이다.

 

class MaxBinaryHeap {
  constructor() {
    values: [];
  }
}

 

삽입 메서드 (Insert)

새로운 노드 삽입 시 Value List 맨 뒤에 값을 Push해주면 된다. 값을 넣는 삽입 자체는 어렵지 않지만, 추가적으로 고려해야 하는 부분이 존재한다.

 

버블 업

노드들을 배열에 맵핑한 상태에서, 새로운 노드가 들어올 경우 말단(Leaf)에서 시작하여 버블 업을 통해 이진 힙의 조건을 만족할 수 있게 위치를 계속 변경하는 과정을 거친다. 이를 통해 큰 값을 갖는 노드가 상단에 위치하게 된다. (최대 이진 힙 기준)

 

변경되는 위치는 삽입된 노드의 부모 노드로, 삽입된 노드의 크기 값이 더 클 경우 서로의 인덱스를 바꿔준다.

 

Insert 메서드와 bubbleUp 메서드 처리를 합쳐도 되고, bubbleUp 메서드를 따로 구현하여 호출하는 형식으로 사용할 수도 있다. 아래 코드에서는 따로 구현하고, 호출하여 사용하는 방식으로 구현하였다.

 

  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;
    }
  }

 

제거 메서드 (Remove, ExtraMax)

삽입은 끝단 노드에서, 제거는 시작단 노드(루트)에서 처리되는 것이 일반적이다. 우선순위 큐에서는 우선순위에 따라 노드가 정렬되고, 가장 높은 우선순위를 갖는 루트의 노드 값이 가장 먼저 제거된다.

 

싱크다운

제거 후에는 새로운 값이 루트도 들어와야 한다. 일반적으로 가장 말단에 위치한 노드 값을 가져온다. 그 후 해당 값을 크기에 맞게 이동시킨다. 자식 노드 값들이 현재 노드보다 클 경우 위치를 변경하는데, 좌우 모두 현재 노드보다 큰 값이라면 둘 중 더 큰 값을 갖는 노드와 위치를 변경한다.

 

  extractMax() {
    const root = this.values[0];
    const end = this.values.pop();

    if (this.values.length > 0) {
      his.values[0] = end;
      this.sinkDown();
    }
    t;
    return root;
  }
  sinkDown() {
    let idx = 0;
    const element = this.values[0];
    const length = this.values.length;

    while (true) {
      let leftChildIndex = 2 * idx + 1;
      let rightChildIndex = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      // 자식 노드가 존재하는지 확인 필요
      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];

        if (leftChild > element) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];

        if ((swap === null && rightChild > element) ||
        (swap !== null && rightChild > leftChild)) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.valus[swap];
      this.values[swap] = element;
    }
  }

 

우선순위 큐 (Priority Queue)

각 노드 요소가 그에 해당하는 우선순위를 가지는 데이터 구조 개념이다. 우선순위 값이 낮은 요소일수록 더 높은 우선순위를 갖고 먼저 처리된다.

 

클래스 셋업 : PriorityQueue

기본적인 구조는 빈 리스트를 갖는 이진 힙과 동일하지만, 추가적으로 Priority 프로퍼티를 갖는 노드 클래스를 추가로 필요로 한다. 사용되는 힙 알고리즘은 최소 이진 힙이며, 값 자체를 비교하는 것이 아닌 우선순위를 기준으로 비교한다. 삽입 / 제거 메서드는 Enqueue, Dequeue로 선언하여 사용.

 

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

  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    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.priority <= parent.priority) break;

      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  dequeue() {
    const root = this.values[0];
    const end = this.values.pop();

    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }

    return root;
  }

  sinkDown() {
    let idx = 0;
    const element = this.values[0];
    const length = this.values.length;

    while (true) {
      let leftChildIndex = 2 * idx + 1;
      let rightChildIndex = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      // 자식 노드가 존재하는지 확인 필요
      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];

        if (leftChild.priority < element.priority) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];

        if ((swap === null && rightChild.priority > element.priority)
		|| (swap !== null && rightChild.priority > leftChild.priority)) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.valus[swap];
      this.values[swap] = element;
    }
  }
}

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

let heap = new PriorityQueue();
heap.enqueue(55);

 

이진 힙의 빅오 복잡도

이진 힙은 삽입 / 제거 과정 모두 뛰어난 성능을 보인다. 한 레벨 당 하나의 노드만 비교하면 되기 때문에, O(log N)의 복잡도를 갖게 된다.