🔍 힙 (Heap)

1️⃣ 개념

힙은 최댓값 또는 최솟값을 빠르게 꺼내기 위한 완전이진트리 기반 자료구조로 우선순위가 가장 높은 값을 빠르게 찾기 위한 구조입니다.

🧐 예시

게임에서 데미지가 가장 큰 스킬부터 사용하고 싶다면?

• 스킬들을 저장
• 가장 강한 스킬 먼저 사용
• 다음으로 강한 스킬

👉 이런 “우선순위 처리”가 바로 힙

2️⃣ 언제 힙을 쓰는가?

✅ 우선순위가 중요한 문제

가장 큰 값 / 가장 작은 값을 반복적으로 꺼내야 할 때

• 가장 큰 값 K번 제거
• 최소 비용 선택
• 상위 N개 유지

✅ 정렬이 필요 없는 경우

• 전체 정렬 ❌
• 특정 값만 필요 ⭕

3️⃣ 힙의 종류

🔹 Max Heap (최대 입)

부모 ≥ 자식

• 가장 큰 값이 루트
• .pop() → 최대값 반환

🔹 Min Heap (최소 힙)

부모 ≤ 자식

• 가장 작은 값이 루트
• .pop() → 최소값 반환

4️⃣ 핵심 아이디어

1. 완전 이진 트리

• 왼쪽부터 차곡차곡 채워짐

2. 힙 조건 유지

• 부모와 자식 간의 관계만 유지

5️⃣ 기본 구조

🧐 Max Heap 기준

// 데이터를 넣고 힙 노드 구조를 만드는 함수
function push(heap, value) {
	heap.push(value);

	let idx = heap.length - 1;

	// 부모보다 클 경우, 최상위 노드까지 올라가며 정렬
	while (idx > 0) {
		// 현재 위치에서 부모 노드의 위치 계산
		let parent = Math.floor((idx - 1) / 2);

		// 부모가 더 크면 조건 만족 → 종료 (Max Heap 유지)
		if (heap[parent] >= heap[idx]) break;

		// 부모 < 자식이면 swap (위로 이동)
		[heap[parent], heap[idx]] = [heap[idx], heap[parent]];
		idx = parent;
	}
}
// 데이터를 빼고 힙 노드 구조 만드는 함수
function pop(heap) {
    if (heap.length === 0) return null;
    if (heap.length === 1) return heap.pop();

    const top = heap[0]; // 최대값(최상위)
    heap[0] = heap.pop(); // 마지막 값을 루트로

    let idx = 0;

    // 자식 노드보다 클 경우 정지
    while(true) {
        // 자식 좌,우, 부모(최초에 최상단) 노드 idx 
        let left = idx * 2 + 1;
        let right = idx * 2 + 2;
        let largest = idx;

        // 자식(좌) 보다 부모가 작을 경우 최대 값 변경
        if (left < heap.length && heap[left] > largest) largest = heap[left];
        // 자식(우) 보다 부모가 작을 경우 최대 값 변경
        if (right < heap.length && heap[right] > largest) largest = heap[right];
        // 변경 되지 않은 경우 최상단은 최대값으로 정지
        if (largest === idx) break;
        // 변경된 경우 힙 구조에 넣기(left or right)
        [heap[idx], heap[largest]] = [heap[largest], heap[idx]];
        idx = largest
    }

    return top;
}

🧪 전체 흐름 예제

const heap = [];

push(heap, 4);   // [4]
push(heap, 10);  // [10, 4]
push(heap, 3);   // [10, 4, 3]
push(heap, 8);   // [10, 8, 3, 4]

push 과정

// 마지막 8추가 과정
      10
     /  \
    4    3

+ 8 // 8 추가

→ 아래에 붙임

    10
   /  \
  4    3
 /
8

→ 위로 올림

    10
   /  \
  8    3
 /
4

console.log(pop(heap)); // 10 console.log(pop(heap)); // 8 console.log(pop(heap)); // 4 console.log(pop(heap)); // 3

pop 과정

// 10 빼는 과정 
   -10
   /  \
  8    3
 /
4

// 마지막 노드(4)를 위로 올림
   4
  / \
 8   3

// 자식 노드 중 더 큰 값(8)과 비교 → swap
   8
  / \
 4   3

✍️ 한 줄 정리

힙은 전체 정렬 없이도 최댓값(또는 최솟값) 을 빠르게 꺼내기 위한 트리 기반 자료구조입니다.