힙 개념 정리

힙이란?

완전 이진 트리 형태의 자료구조이다.

우선순위가 있는 데이터를 저장하고 관리하는  특별한 트리다.

 

완전 이진 트리란?

1. 모든 레벨이 왼쪽부터 차례대로 채워진다.
2. 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있어야 한다.
3. 앞 줄부터 왼쪽에서 오른쪽에서 차례대로 앉은 것처럼, 노드들이 순서대로 채워진다.

 

완전 이진 트리 예시

 

완전 이진 트리가 아닌 예시

 

힙의 종류

• 최대 힙: 부모 노드가 자식 노드보다 항상 큰 힙 자료구조 (부모 > 자식)
• 최소 힙: 부모 노드가 자식 노드보다 항상 작은 힙 자료구조 (부모 < 자식)

힙의 특징

• 항상 완전 이진 트리 형태를 유지
• 부모 - 자식 간의 대소 관계만 중요(형제 노드 간의 관계는 상관 없음)
• 배열로 구현하면 쉽게 관리 가능

최소 힙 예시

// 배열
[0, 1, 2, 3, 4, 5, 6]

// 배열 -> 힙 변환 그림

       0
     /   \
    1     2
  /   \ /   \ 
 3    4 5    6

 

최소 힙 구현 예시

class MinHeap {
 constructor() {
  this.heap = [];
 }
 
 // 부모 인덱스 구하기
 // (현재 인덱스 -1) / 2 => 소수점 버리기
 getParentIndex(index) {
   return Math.floor((index - 1) / 2);
 }
 
 // 값 추가하기
 // 맨 뒤에 넣고 -> 부모 노드와 계속 비교하며 변경
 insert(value) {
  this.heap.push(value);
  this.bubbleUp(this.heap.length - 1);
 }
 
 // 위로 올리기 (새로운 값 추가 시)
 bubbleUp(index) {
  while(index > 0){
   const parentIndex = this.getParentIndex(index);
   if (this.heap[parentIndex] <= this.heap[index]) break;
   
   // 부모와 위치 교환
   [this.heap[index], this.heap[parentIndex]] = 
   [this.heap[parentIndex], this.heap[index]];
   index = parentIndex;
  }
 }
 
 // 최소값 꺼내기
 remove() {
  if(this.heap.length === 0) return null;
  
  const min = this.heap[0];
  const last = this.heap.pop();
  
  if(this.heap.length > 0) {
   this.heap[0] = last;
   this.bubbleDown(0);
  }
  
  return min;
 }
}

// 사용 예시
const heap = new MinHeap();
heap.insert(5);
heap.insert(3);
heap.insert(7);
heap.insert(1);

console.log(heap.remove()); // 1
console.log(heap.remove()); // 3

 

1. getParentIndex 설명

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

       0
     /   \
    1     2
  /   \ /   \
 3    4 5    6
 
 // 위 트리 예시를 배열로 표현할 경우 [0, 1, 2, 3, 4, 5, 6]

 

규칙

• 노드 1의 부모는 0 : (1-1)/2 = 0
• 노드 2의 부모는 0 : (2-1)/2 = 0
• 노드 3의 부모는 1 : (3-1)/2 = 1
• 노드 4의 부모는 1 : (4-1)/2 = 1
• 노드 5의 부모는 2 : (5-1)/2 = 2
• 노드 6의 부모는 2 : (6-1)/2 = 2

수식 설명

1. 자식 노드의 인덱스와 부모 노드의 인덱스 사이에는 다음과 같은 관계가 성립한다.

• 왼쪽 자식 = 부모 * 2 + 1
• 오른쪽 자식 = 부모 * 2 + 2

2. 이 관계를 역으로 풀면 

• 부모 = (자식 - 1) / 2

3. 소수점을 버리기 위해 Math.floor 사용

 

2. insert 설명

insert(value) {
 // 1. 새로운 값을 배열의 마지막에 추가
 this.heap.push(value);
 
 // 2. 추가된 값을 올바른 위치로 이동 (bubbleUP 호출)
 this.bubbleUp(this.heap.length - 1);
}

bubbleUp(index) {
 // index가 0이 되면 중단
 while (index > 0) {
  // 1. 현재 노드의 부모 인덱스 계산
  const parentIndex = this.getParentIndex(index);
  
  // 2. 부모 값이 현재 값보다 작거나 같으면 종료
  // (최소 힙의 경우 부모가 자식보다 작아야 함)
  if(this.heap[parentIndex] <= this.heap[index]) break;
  
  // 3. 부모 값이 더 크면 위치 교환
  [this.heap[index], this.heap[index]] =
  [this.heap[parentIndex], this.heap[index]];
  
  // 4. 교환 후 인덱스를 부모 위치로 업데이트
  index = parentIndex;
 }
}

 

예시) 최소 힙에 [5, 8, 10]이 있는 상태에서 3을 삽입하는 경우

초기 상태 : // [5, 8, 10]

         5
       /   \
      8     10
  
1. 마지막에 3 추가 : // [5, 8, 10, 3]

          5
        /   \
       8     10
      /
     3
    
2. bubbleUp 시작 (3과 부모인 8 비교): // [5, 3, 10, 8]

           5
         /   \
        3     10
       /
      8
      
3. 계속해서 bubbleUp (3과 부모인 5 비교): // [3, 5, 10, 8]

           3
         /   \
        5     10
       /
      8
      
4. 완료! (부모가 더 작은 값이 없음)

 

3. remove 설명

힙에서 최소값(루트 노드) 반환 및 제거 & 재정렬

remove() {
 // 1. 힙이 비어있으면 null 반환
 if(this.heap.length === 0) return null;
 
 // 2. 루트 노드(최솟값) 저장
 const min = this.heap[0];
 
 const last = this.heap.pop();
 
 // 4. 힙에 노드가 남아있다면
 if(this.heap.length > 0) {
  // 마지막 노드를 루트로 이동
  this.heap[0] = last;
  // 루트에서부터 아래로 내려가며 재정렬
  this.bubbleDown(0);
 }
 
 // 5. 최솟값 반환
 return min;
}

 

예시) 최소 힙 [1, 3, 5, 4]에서 remove를 실행하는 경우: 

1. 초기 상태:
     1
   /   \
  3     5
 /
4

2. 루트 노드(1) 제거 후, 마지막 노드(4)를 루트로 이동:
     4
   /   \
  3     5

3. bubbleDown 시작 (4와 자식들 중 작은 값인 3과 비교 후 교환):
     3
   /   \
  4     5

4. 완료! (더 이상 자식이 더 작지 않음)

 

4. bubbleDown 함수

힙의 특성을 유지하기 위해 노드를 아래로 내려가며 재정렬하는 과정

bubbleDown(index){
 while(true) {
  // 1. 현재 노드를 가장 작은 값으로 가정
  let smallest = index;
  
  // 2. 왼쪽, 오른쪽 자식의 인덱스 계산
  const leftChild = 2 * index + 1; // 왼쪽 자식 인덱스
  const rightChild = 2 * index + 2; // 오른쪽 자식 인덱스
  
  // 3. 왼쪽 자식이 있고, 현재 노드보다 작은지 확인
  if(leftChild < this.heap.length && this.heap[leftChild] < this.heap[index]) {
   smalles = leftChild;
  }
  
  // 4. 오른쪽 자식이 있고, 현재까지의 최소값보다 작은지 확인
  if(rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
   smallest = rightChild;
  }
  
  // 5. 교환이 필요없으면 (현재 노드가 자식들보다 작으면) 종료
  if (smallest === index) break;
  
  // 6. 값 교환
  [this.heap[index], this.heap[smallest]] = 
  [this.heap[smallest], this.heap[index]];
  
  // 7. 교환된 위치로 이동하여 계속 진행
  index = smallest;
 }
}

 

예시) 다음과 같은 최소 힙이 있다고 가정해보자

초기 상태 (7이 루트에 있는 상태):
     7
   /   \
  1     3
 / \   / \
2  5  4   

1회차 반복:
- 왼쪽 자식(1)과 오른쪽 자식(3) 중 1이 더 작음
- 7과 1을 교환
     1
   /   \
  7     4
 / \   /
2  5  3

2회차 반복:
- 왼쪽 자식(2)과 오른쪽 자식(5) 중 2가 더 작음
- 7과 2를 교환
     1
   /   \
  2     3
 / \   /
7  5  4

3회차 반복:
- 더 이상 자식이 없거나 자식들이 더 크므로 종료

최종 상태:
     1
   /   \
  2     3
 / \   /
7  5  4

 

핵심 정리

1. 자식 인덱스 계산

const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;

2. 자식 노드 존재 확인

leftChild < this.heap.length

3. 자식 노드와 비교

if (this.heap[leftChild] < this.heap[smallest])

4. 교환 필요성 확인

if (smallest === indext) break;

 

문제 풀어보기 (프로그래머스)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

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

  // 최소힙 배열 중 가장 마지막에 두고, bubbleUp 함수를 통해 최소힙 구조로 정렬
  push(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  // 최소힙 배열 중 최소값(root)를 반환하고, 마지막 요소를 root로 올린 후 bubbleDown 함수를 통해 최소힙 구조로 정렬
  pop() {
    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;
  }

  // 마지막 요소를 부모 요소와 비교하며 더 작은 경우 부모와 자리를 바꾼다.
  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[index], this.heap[parentIndex]] = [
        this.heap[parentIndex],
        this.heap[index],
      ];
      index = parentIndex;
    }
  }

  bubbleDown() {
    let index = 0;
    while (true) {
      // 현재 루트에 있는 요소를 최소 인덱스라고 가정
      let smallest = index;

      // 왼쪽 자식 인덱스
      const leftChild = 2 * index + 1;
      // 오른쪽 자식 인덱스
      const rightChild = 2 * index + 2;

      // 왼쪽 자식 인덱스가 배열 길이보다 작고 (존재하고),
      // 왼쪽 자식 요소가 현재 요소보다 작으면 최소 인덱스를 왼쪽 자식 인덱스로 변경
      if (
        leftChild < this.heap.length &&
        this.heap[leftChild] < this.heap[smallest]
      ) {
        smallest = leftChild;
      }

      // 오른쪽 자식 인덱스가 배열 길이보다 작고 (존재하고),
      // 오른쪽 자식 요소가 현재 요소보다 작으면 최소 인덱스를 오른쪽 자식 인덱스로 변경
      if (
        rightChild < this.heap.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;
    }
  }

  size() {
    return this.heap.length;
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();
  let count = 0;

  // 모든 스코빌 지수를 힙에 넣기
  scoville.forEach((s) => minHeap.push(s));

  // 가장 작은 값이 K보다 작은 동안 반복
  while (minHeap.size() >= 2 && minHeap.heap[0] < K) {
    // 가장 작은 값 두 개를 꺼내서 섞은 후 힙에 넣기
    const first = minHeap.pop();
    const second = minHeap.pop();
    const newScoville = first + second * 2;
    minHeap.push(newScoville);

    // 섞었기 때문에 count + 1
    count++;
  }

  // 최소 힙 배열 중 최소값(root)이 K 이상인지 확인
  // 여전히 없다면 -1 반환
  return minHeap.heap[0] >= K ? count : -1;
}

 

너무 어려워서 튜터님이 푸신거 그대로 .... 복습 반드시 필필필 !