자료구조와 알고리즘, Tree, Binary Heap

 

이진 힙(Binary Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 힙 속성을 만족하는 자료 구조입니다. 힙 속성은 다음과 같은 두 가지 형태로 구분됩니다:

1. 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조.
2. 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조.

출처 [https://cs.slides.com/colt_steele/heaps#/13/0/2]

이진 힙의 특징

1. 완전 이진 트리: 이진 힙은 항상 완전 이진 트리입니다. 즉, 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 경우 왼쪽부터 차례대로 노드가 채워져 있습니다.
2. 힙 속성: 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같고, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.

이진 힙의 구현

이진 힙은 주로 배열을 사용하여 구현됩니다. 배열을 사용하면 부모와 자식 노드 간의 관계를 인덱스를 통해 쉽게 접근할 수 있습니다.

• 부모 노드의 인덱스: Math.floor((i - 1) / 2)
• 왼쪽 자식 노드의 인덱스: 2 * i + 1
• 오른쪽 자식 노드의 인덱스: 2 * i + 2

출처 [https://cs.slides.com/colt_steele/heaps#/13/0/2]

출처 [https://cs.slides.com/colt_steele/heaps#/26/0/0]

출처 [https://cs.slides.com/colt_steele/heaps#/26/0/0]

출처 [https://cs.slides.com/colt_steele/heaps#/37]

출처 [https://cs.slides.com/colt_steele/heaps#/37

최대 힙의 구현 (자바스크립트 예제)

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

  insert(value) {
    // Push the value into the values property on the heap
    // Bubble the value up to its correct spot!
    this.values.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    // Create a variable called index which is the length of the values property - 1
    // Create a variable called parentIndex which is the floor of (index-1)/2
    // Keep looping as long as the values element at the parentIndex is less than the values element at the child index
    // Swap the value of the values element at the parentIndex with the value of the element property at the child index
    // Set the index to be th parentIndex, and start over!

    let idx = this.values.length - 1;
    const element = this.values[idx];

    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parentElement = this.values[parentIdx];

      if (element <= parentElement) break;

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

  extractMax() {
    // Swap the first value in the values property with the last one
    // Pop from the values property, so you can return the value at the end
    // Have the new root "sink down" to the correct spot
    // Your parent index starts at 0 (the root)
    // Find the index of the left child: 2 * idx + 1
    // Find the index of the right child: 2 * idx + 2
    // If the left or right child is greater than the element > swap
    // If both left and right children are larger, swap with the largest child
    // The child index you swapped to now becomes the new parent index
    // Keep looping and swapping until neither child is larger than the element
    // Return the old root
    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) {
      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;
    }
  }
}

let maxBinaryHeap = new MaxBinaryHeap();
maxBinaryHeap.insert(41);
maxBinaryHeap.insert(39);
maxBinaryHeap.insert(33);
maxBinaryHeap.insert(18);
maxBinaryHeap.insert(27);
maxBinaryHeap.insert(12);

maxBinaryHeap.insert(55);
// [41,39,33,18,27,12,55]
//  0  1  2  3  4  5  6

console.log('maxBinaryHeap:', maxBinaryHeap);

최소 힙의 구현 (자바스크립트 예제)

최소 힙은 최대 힙과 거의 동일한 방식으로 구현되지만, 힙 속성을 유지하기 위해 부모와 자식 노드의 크기 비교가 반대입니다.

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

  insert(value) {
    // Push the value into the values property on the heap
    // Bubble the value up to its correct spot!
    this.values.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    // Create a variable called index which is the length of the values property - 1
    // Create a variable called parentIndex which is the floor of (index-1)/2
    // Keep looping as long as the values element at the parentIndex is less than the values element at the child index
    // Swap the value of the values element at the parentIndex with the value of the element property at the child index
    // Set the index to be th parentIndex, and start over!

    let idx = this.values.length - 1;
    const element = this.values[idx];

    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parentElement = this.values[parentIdx];

      if (element >= parentElement) break;

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

  extractMax() {
    // Swap the first value in the values property with the last one
    // Pop from the values property, so you can return the value at the end
    // Have the new root "sink down" to the correct spot
    // Your parent index starts at 0 (the root)
    // Find the index of the left child: 2 * idx + 1
    // Find the index of the right child: 2 * idx + 2
    // If the left or right child is greater than the element > swap
    // If both left and right children are larger, swap with the largest child
    // The child index you swapped to now becomes the new parent index
    // Keep looping and swapping until neither child is larger than the element
    // Return the old root
    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) {
      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;
    }
  }
}

let minBinaryHeap = new MinBinaryHeap();
minBinaryHeap.insert(41);
minBinaryHeap.insert(39);
minBinaryHeap.insert(33);
minBinaryHeap.insert(18);
minBinaryHeap.insert(27);
minBinaryHeap.insert(12);

minBinaryHeap.insert(55);
// [12, 27, 18, 41, 33, 39, 55]
//  0  1  2  3  4  5  6

console.log('minBinaryHeap:', minBinaryHeap);

이진 힙의 시간 복잡도

• 삽입 및 삭제: O(log n) - 힙의 높이가 log n이기 때문에 삽입과 삭제 모두 log n 시간에 수행됩니다.
• 검색: O(n) - 힙에서 특정 값을 검색하려면 모든 노드를 확인해야 할 수 있습니다.

이진 힙은 우선순위 큐를 구현할 때 주로 사용됩니다. 최소 힙은 우선순위가 낮은 요소를 먼저 처리해야 할 때, 최대 힙은 우선순위가 높은 요소를 먼저 처리해야 할 때 유용합니다.