Heap

 

Heap

Heap은 특정 기준에 따라 항상 정렬 상태를 유지하는 트리 기반 자료구조입니다.

 

 

Heap은 아래 조건만 보장합니다.

MinHeap

• 부모 ≤ 자식
• 가장 작은 값이 항상 맨 위(root)

MaxHeap

• 부모 ≥ 자식
• 가장 큰 값이 항상 맨 위(root)

그래서 Heap은 이렇게 쓰입니다.

상황	이유
가장 작은 값 / 큰 값 빠르게 꺼내기	O(1)
삽입 / 삭제	O(log n)
정렬 없이 Top K 유지	효율적

 

---

PriorityQueue = Heap

자바스크립트 / 타입스크립트에서 흔히 쓰는 MinPriorityQueue 는 MinHeap 구현체입니다.

const minHeap = new MinPriorityQueue<number>();

여기서 중요한 메서드 3개

minHeap.enqueue(value); // 삽입
minHeap.dequeue();      // 최우선 값 제거
minHeap.front();        // 최우선 값 조회

 

minHeap.front();

• "먼저 들어온 값"이 아닙니다
• 우선순위 기준으로 가장 앞에 있는 값 = 가장 작은 값

minHeap.enqueue(5);
minHeap.enqueue(1);
minHeap.enqueue(10);
minHeap.enqueue(3);

minHeap.front(); // 1

• 입력 순서와 무관하게 최소값이 나옵니다.

 

---

Heap으로 k번째 큰 수 구하기

대표적인 Heap 활용 문제입니다.

문제 요약

• 배열 nums
• k번째로 큰 수 반환
• 크기 k짜리 MinHeap 유지
• Heap에는 항상 상위 k개 값만 존재
• Heap의 최소값 = k번째로 큰 값

function findKthLargest(nums: number[], k: number): number {
  const minHeap = new MinPriorityQueue<number>();

  for (const num of nums) {
    if (minHeap.size() < k) {
      minHeap.enqueue(num);
    } else if (num > minHeap.front()) {
      minHeap.enqueue(num);
      minHeap.dequeue();
    }
  }

  return minHeap.front();
}

enqueue → dequeue 순서인가?

이 두 줄은 세트입니다.

minHeap.enqueue(num);
minHeap.dequeue();

의미는 단순합니다.

새 후보를 넣고, k+1명 중 꼴찌를 탈락

예시 (k = 3)

기존 힙: [4, 7, 9]
num = 10

enqueue → [4, 7, 9, 10]
dequeue → [7, 9, 10]

• 항상 상위 3개만 유지