[JS] 이진 힙

여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리. 짧게 힙(Heap)이라고 줄여서 부르기도 한다.

 

이진 힙

이진 힙은 이진탐색트리(BST)와 아주 유사하지만, 다음과 같은 몇 가지 규칙이 다르다.

• 최대 이진 힙(MaxBinaryHeap)에서는 부모 노드가 항상 자식 노드들보다 커야 한다.
• 최소 이진 힙(MinBinaryHeap)에서는 부모 노드가 항상 자식 노드들보다 작아야 한다.

• • 이진 힙에서 부모와 자식 노드 간의 관계는 위와 같이 크거나 작아야 하지만, 형제 노드들 간의 관계에는 그러한 규칙이 없다.
  • 이진 힙은 언제가 가능한 가장 적은 최적의 공간만을 차지한다.

아래 이미지와 같은 트리가 최대 이진 힙(MaxBinaryHeap) 이다. 부모 노드들이 항상 자식 노드들보다 크며, 형제 노드들 간에는 특별한 순서가 없다.

 

최대 이진 힙 MaxBinaryHeap ,최소 이진 힙 MinBinaryHeap

 

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

  insert(element) {
    this.values.push(element);
    //삽입하려는 요소를 기존 배열의 끝에 push
    this.bubbleUp();
    //그리고 부모노드와 크기 비교 후 스왑하면서 끌어올린다 
  }

  bubbleUp() {
  //배열 마지막 인덱스
    let idx = this.values.length - 1;
    const element = this.values[idx];
    
    // 인덱스 0이 되면 root자리이기 때문에 저 올라갈 곳이 없다.
    while (idx > 0) {    
    //부모 위치 찾는 공식 (n-1/2) 사용
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      // 삽입한 요소가 부모요소보다 작거나 같으면 자리바꿀 필요 없어서 break
      if (element <= parent) break;
      //스왑
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

// root에 가장 큰 값을 제거하는 메서드
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      //루트자리에 마지막 요소를 넣는다
      this.sinkDown();
    }
    return max;
  }
  
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
    //부모 위치로부터 자식 위치 찾는 공식을 이용하여 left, right 자식의 위치를 구한다.
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      
      let leftChild;
      let rightChild;
      let swap = null;

 //왼쪽 자식이 있으면
      if (leftChildIdx < length) {
      //왼쪽 자식 값을 할당하고
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
        //왼쪽 자식이 현재 위치값보다 더 크면 스왑한다.
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
        //스왑이 null이고 rightChild가 현재 위치값보다 크거나,
        //스왑에 왼쪽자식이 있고 오른쪽값이 왼쪽보다 크면
        //오른쪽 자식을 스왑에 할당
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }
      //여전히 swap이 null이면 반복문을 break
      if (swap === null) break;
      //스왑값과 element를 스왑해준다
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

 

extraMax 란?

최상단 root(가장 큰 값) 을 제거하고

root자리에 가장 최근에 추가한 요소를 넣는다

그 후 sinkDown 메서드로 아래로 내려 보내는것

 

 

우선순위큐 Priority Queue

 우선순위 큐는 각각의 요소가 개별 우선순위를 갖는 자료구조다. 높은 우선순위를 가진 요소는 낮은 우선순위를 가진 요소보다 앞에 온다.

우선순위 큐가 보통 힙(Heap)을 사용하기 때문에, 이 둘이 같거나 관계가 있다고 생각할 수도 있으나, 우선순위 큐와 힙(Heap)은 상관관계가 없다. 우선순위 큐는 단지 추상적인 개념에 불과하며, 힙 외에 배열이나 리스트 등의 다른 방식(물론 느릴 수는 있음)으로도 구현할 수 있다.

하지만 힙(Heap)이 더 좋은 성능(삽입, 제거 모두 O(log n))을 갖기 때문에, 힙으로 우선순위 큐를 구현해보자.

 

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

  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() { // 이진힙에서 만든 extractMax
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
  sinkDown() {
    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;
      let rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        // 최소이진힙이라 부등호 방향 반대, 비교하는값은 priority 프로퍼티
        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;
    }
  }
}

 

이진 힙의 성능

삽입 O(log n)

제거 O(log n)

탐색 O(N)

 

결론

• 이진 힙은 힙의 한 종류이며, 힙은 트리의 한 종류이다.
• 이진 힙은 그 자체로도 유용하지만, 우선순위 큐와 같은 다른 데이터 구조를 코딩하는 데에도 유용하다.
• 이진 힙은 크게 최대이진힙과 최소이진힙으로 나뉜다.
  • 최대이진힙에서는 모든 부모가 두 자식보다 크다.
  • 최소이진힙에서는 모든 부모가 두 자식보다 작다.
• 이진 힙은 왼쪽에서부터 오른쪽으로 채워나가기 때문에, 한 쪽으로 치우친 트리는 나오지 않고 피라미드 모양에 가깝게 유지한다.
• 약간의 수학공식을 활용하면, 노드의 포인터 같은 것 없이도 배열만을 가지고 힙을 구현할 수도 있다. 물론 직접 클래스를 만들고 노드를 활용하여 힙을 만들 수도 있다.