[알고리즘] 힙 - Heap

힙(Heap)

완전 이진 트리의 일종으로, 최댓값 또는 최솟값을 빠르게 찾아내기 위한 자료구조.
효율적인 데이터 관리와 처리가 필요한 다양한 알고리즘과 시스템에서 사용되며, 주로 우선순위 큐를 구현할 때 사용됨

우선순위 큐는 큐 자료구조에 우선순위 개념을 도입해 데이터가 들어오면 우선순위에 따라 정렬하고 우선순위가 높은 데이터가 먼저 빠져나가는 구조

종류

1. 최대 힙(Max Heap) - 부모 노드의 값이 자식 노드의 값보다 크거나 같음
2. 최소 힙(Min Heap) - 부모 노드의 값이 자식 노드의 값보다 작거나 같음

특징

1. 완전 이진 트리 구조 - 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워짐

2. 순서 속성 - 반정렬 상태

   • 최대 힙은 부모 노드 >= 자식노드
   • 최소 힙은 부모 노드 <= 자식노드

3. 중복 허용 - 이진 트리와 달리 중복된 값을 허용

4. 효율적인 연산 - log n의 시간 복잡도를 가짐

힙의 구현

• 힙은 트리 구조이지만 js에서 이를 구현하기 위해서 배열을 사용
• 노드 번호를 쉽게 구별하기 위해서 배열의 0번 인덱스는 사용하지 않는 것이 편함
  • 부모 노드 인덱스 = Math.floor(자식 인덱스 / 2)
  • 왼쪽 자식 노드 인덱스 = 부모 인덱스 * 2
  • 오른쪽 자식 노드 인덱스 = (부모 인덱스 * 2) + 1

삽입

최소 힙을 예로 들자면,

1. 새로운 요소를 마지막 노드에 삽입
2. 부모 노드와 우선 순위를 비교하고 위치를 변경해야 한다면 실행
3. 힙의 성질이 true가 될 때까지 부모 노드와 비교를 반복

1. 새로운 요소 2를 마지막 노드에 삽입하고 부모 노드와 비교
   

2. 부모 노드와 위치를 변경하고 다시 부모 노드와 비교
   

3. 힙의 성질을 만족할 때까지 반복
   

삭제

1. 루트(최상위) 노드를 삭제하고 마지막 노드를 루트 노드 자리에 옮김
2. 힙의 성질에 맞게 자식 노드와 비교하며 재정렬

1. 루트 노드 1을 삭제하고 마지막 노드 13을 옮김
   

2. 우선 순위가 높은 3과 비교해서 재정렬
   

3. 힙의 성질을 만족할 때까지 반복
   
   

코드

class MinHeap {
  // 0번 인덱스는 사용하지 않기 위해 첫 번째 요소로 null 추가
  constructor() {
    this.heap = [null];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  
  bubbleUp() {
    let index = this.heap.length - 1;
    const insertedNode = this.heap[index]; // 새로 삽입된 노드

    // 비교 대상이 최상위 부모 노드가 될 때까지 반복
    while (index > 1) {
      const parentIndex = Math.floor(index / 2); // 비교할 부모 노드
      // 삽입된 노드의 값이 부모 노드의 값보다 작다면
      // 삽입된 노드 자리에 부모 노드의 값을 넣고, 
      // 다음 비교를 위해 현재 인덱스는 부모 인덱스로 변경
      if (insertedNode < this.heap[parentIndex]) {
        this.heap[index] = this.heap[parentIndex];
        // 구조 분해 할당으로 변경하는 것도 가능
        // [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
        index = parentIndex;
        
      // 삽입된 노드의 값이 부모 노드의 값보다 크거나 같다면 반복문 중단
      } else break;
    }

    // 현재 인덱스에 삽입된 노드의 값을 넣어줌
    this.heap[index] = insertedNode;
  }

  remove() {
    // 트리에 노드가 1개일 경우, 삭제 및 반환
    if (this.heap.length === 2) return this.heap.pop();
    
    const root = this.heap[1];
    // 마지막 노드를 삭제하고 루트 노드로 이동
    this.heap[1] = this.heap.pop();
    this.bubbleDown();
    // 삭제한 노드 반환
    return root;
  }

  bubbleDown() {
    let index = 1;
    const rootNode = this.heap[index]; // 처음 비교할 루트 노드
    
    // 노드가 마지막 레벨로 갈 때까지 반복
    while ((index * 2) < this.heap.length) {
      const leftChildIndex = index * 2;
      const rightChildIndex = index * 2 + 1;
      
      // 오른쪽 자식이 존재할 때, 왼쪽과 오른쪽 자식의 크기 비교
      const smallerChildIndex = 
        rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[leftChildIndex] 
        ? rightChildIndex 
        : leftChildIndex;
      
      // 루트 노드가 자식 노드보다 크다면
      // 루트 노드 자리에 자식 노드의 값을 넣고,
      // 다음 비교를 위해 인덱스는 자식 인덱스로 변경
      if (rootNode > this.heap[smallerChildIndex]) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
        
      // 루트 노드가 자식 노드보다 크거나 같다면 반복문 중단
      } else break;
    }

    // 현재 인덱스에 처음 루트 노드의 값을 넣어줌
    this.heap[index] = rootNode;
  }
}