자료구조 힙(heap)

힙을 사용하는 이유

• 우선순위 큐
  • 데이터가 들어 온 순서에 상관 없이 우선 순위가 높은 데이터 순으로 처리해야 할 때
  • 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나감
  • ex) 작업 스케줄링, CPU 스케줄링

    우선순위 큐란?
    우선순위 큐는 큐의 한 종류로, 데이터의 삽입 순서와 상관없이 우선순위가 높은 데이터부터 처리하는 구조입니다. 힙은 우선순위 큐를 효율적으로 구현할 수 있는 자료구조입니다.
    최소 힙을 이용하면 가장 낮은 우선순위의 데이터를, 최대 힙을 이용하면 가장 높은 우선순위의 데이터를 처리할 수 있는 장점이 있습니다

특징

• 완전 이진트리
• 힙 트리는 데이터 중복을 허용함
• 데이터를 최대 혹은 최소값을 빠르게 가져오는게 중요한 상황에서 자주 사용됨
• 힙의 시간 복잡도
  • 데이터를 가지고 올 때O(1)의 시간 복잡도를 가짐
  • 삽입, 삭제에서는 O(logN)의 시간 복잡도를 가짐

    데이터를 삽입하거나 삭제할 때는 O(log N)의 시간 복잡도를 가집니다. 이는 새로운 데이터를 추가하거나 제거한 후 힙 속성을 유지하기 위해 힙을 재정렬하는 작업이 트리의 깊이에 따라 수행되기 때문입니다.
    루트 노드(최솟값 또는 최댓값)를 가져오는 작업은 O(1)의 시간 복잡도를 가집니다. 루트 노드에 최솟값 또는 최댓값이 저장되기 때문입니다.

힙의 종류

• 최대 힙
  • 부모 노드의 값은 항상 자식 노드 보다 크거나 같음
  • 루트 노드 = 트리의 최댓 값
• 최소 힙
  - 부모 노드의 값은 항상 자식 노드의 보다 작거나 같음
  - 루트 노드 = 트리의 최솟 값
  

js로 구현한 힙 (MinHeap)

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

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] > this.heap[index]) {
        this.swap(parentIndex, index);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  remove() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return root;
  }

  heapifyDown() {
    let index = 0;
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      let rightChildIndex = this.getRightChildIndex(index);

      if (
        rightChildIndex < this.heap.length &&
        this.heap[rightChildIndex] < this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = rightChildIndex;
      }

      if (this.heap[index] > this.heap[smallerChildIndex]) {
        this.swap(index, smallerChildIndex);
        index = smallerChildIndex;
      } else {
        break;
      }
    }
  }

  peek() {
    return this.heap[0] || null;
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }
}

코드 설명

• insert
  • 힙의 마지막에 값 추가
    • 힙은 완전 이진 트리이므로 새로운 요소는 항상 배열의 마지막 위치에 삽입해야 함
  • 새로 추가된 요소가 힙의 조건을 만족하는지 확인
  • 새 요소가 부모보다 작은 경우, 부모와 교체하여 위로 올라가고 이 과정을 루트까지 반복
• remove
  • 루트와 마지막 요소 교체 및 제거
    • 힙의 루트(최우선순위, 즉 최솟값)를 제거하고 힙의 마지막 요소를 루트에 재배치
      • 완전 이진트리의 구조를 유지해야 하기 때문
      • 배열에서 가장 효율적으로 제거할 수 있는 요소가 마지막 요소이기 때문(가장 빠르게 제거할 수 있음)
  • 새로운 루트(원래 힙의 마지막 요소)가 힙의 조건을 만족하는지 확인
  • 루트의 값이 자식 노드들보다 큰 경우, 자식들 중 더 작은 값과 교체하면서 아래로 내려감
  • 부모가 값이 제일 작으면 종료