공부하자

Appearance

힙 (Heap) ​

힙은 완전 이진 트리 형태의 자료구조로, 부모 노드와 자식 노드 간에 특정한 대소 관계를 유지한다.
주로 우선순위 큐(Priority Queue)를 구현하거나, 데이터에서 최댓값/최솟값을 빠르게 찾을 때 사용된다.

🔗 Heap 설명 영상
🔗 참고한 기술 블로그

힙의 종류 ​

최대 힙 (Max Heap) ​

부모 노드가 항상 자식 노드보다 크거나 같은 값을 가진다.
→ 루트 노드가 항상 최댓값

       100
      /    \
    50      30
   /  \    /
  20  40  10

최소 힙 (Min Heap) ​

부모 노드가 항상 자식 노드보다 작거나 같은 값을 가진다.
→ 루트 노드가 항상 최솟값

        10
      /    \
    20      30
   /  \    /
  50  40  100

힙의 특징 ​

  • 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워진다.
  • 반정렬 상태: 부모-자식 간의 대소 관계만 보장되고, 형제 간의 순서는 보장되지 않는다.
  • 배열로 표현 가능: 완전 이진 트리 특성상 배열로 효율적으로 표현할 수 있다.

시간 복잡도 ​

연산시간 복잡도
최댓값/최솟값 조회O(1)
삽입 (Insert)O(log n)
삭제 (Delete)O(log n)
힙 생성 (Heapify)O(n)

배열로 힙 표현하기 ​

완전 이진 트리는 배열로 표현할 때, 인덱스 관계가 명확하다.

인덱스:     0    1    2    3    4    5
배열:     [100, 50,  30,  20,  40,  10]

         100 (index 0)
        /    \
      50      30
     (1)      (2)
    /  \      /
   20  40    10
   (3) (4)   (5)

인덱스 관계 (0-based) ​

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

주요 연산 ​

삽입 (Insert) - Bubble Up ​

새 요소를 배열 끝에 추가한 후, 부모와 비교하며 위로 올린다.

javascript
// 최대 힙 기준
insert(value) {
    this.heap.push(value);
    this.bubbleUp();
}

bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2);

        // 부모가 더 크면 정지 (최대 힙 조건 충족)
        if (this.heap[parentIndex] >= this.heap[index]) break;

        // 부모와 교환
        [this.heap[parentIndex], this.heap[index]] =
        [this.heap[index], this.heap[parentIndex]];

        index = parentIndex;
    }
}

삭제 (Extract) - Bubble Down ​

루트를 제거하고, 마지막 요소를 루트로 올린 후 아래로 내린다.

javascript
// 최대 힙 기준 - 최댓값 추출
extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop(); // 마지막 요소를 루트로
    this.bubbleDown();

    return max;
}

bubbleDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        let largest = index;

        // 왼쪽 자식이 더 크면
        if (leftChild < length && this.heap[leftChild] > this.heap[largest]) {
            largest = leftChild;
        }

        // 오른쪽 자식이 더 크면
        if (rightChild < length && this.heap[rightChild] > this.heap[largest]) {
            largest = rightChild;
        }

        // 현재 노드가 가장 크면 종료
        if (largest === index) break;

        // 교환
        [this.heap[index], this.heap[largest]] =
        [this.heap[largest], this.heap[index]];

        index = largest;
    }
}

최대 힙 (Max Heap) ​

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

  // 크기
  size() {
    return this.heap.length;
  }

  // 비어있는지 확인
  isEmpty() {
    return this.heap.length === 0;
  }

  // 최댓값 조회 (제거하지 않음)
  peek() {
    return this.heap[0] ?? null;
  }

  // 삽입
  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex] >= this.heap[index]) break;

      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

  // 최댓값 추출
  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();

    return max;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let largest = index;

      if (leftChild < length && this.heap[leftChild] > this.heap[largest]) {
        largest = leftChild;
      }

      if (rightChild < length && this.heap[rightChild] > this.heap[largest]) {
        largest = rightChild;
      }

      if (largest === index) break;

      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];

      index = largest;
    }
  }
}

const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(50);
maxHeap.insert(30);
maxHeap.insert(20);
maxHeap.insert(100);

console.log(maxHeap.peek()); // 100
console.log(maxHeap.extractMax()); // 100
console.log(maxHeap.extractMax()); // 50
console.log(maxHeap.extractMax()); // 30

최소 힙 (Min Heap) ​

최대 힙에서 비교 연산자만 반대로 바꾸면 된다.

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

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

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      // 최소 힙: 부모가 더 작으면 정지
      if (this.heap[parentIndex] <= this.heap[index]) break;

      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

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

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();

    return min;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let smallest = index;

      if (leftChild < length && this.heap[leftChild] < this.heap[smallest]) {
        smallest = leftChild;
      }

      if (rightChild < length && this.heap[rightChild] < this.heap[smallest]) {
        smallest = rightChild;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }

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

활용 ​

  • 우선순위 큐: 작업 스케줄링, 이벤트 처리
  • 힙 정렬 (Heap Sort): O(n log n) 정렬 알고리즘
  • 다익스트라 알고리즘: 최단 경로 탐색에서 최소 비용 노드 선택
  • Top K 문제: 가장 큰/작은 K개의 요소 찾기
javascript
// Top K 요소 찾기 예시 (최소 힙 활용)
function findTopK(arr, k) {
  const minHeap = new MinHeap();

  for (const num of arr) {
    minHeap.insert(num);

    // 힙 크기가 k를 초과하면 최솟값 제거
    if (minHeap.heap.length > k) {
      minHeap.extractMin();
    }
  }

  return minHeap.heap;
}

// [5, 6, 9] - 가장 큰 3개
console.log(findTopK([3, 1, 4, 1, 5, 9, 2, 6, 5], 3));