🖋️ HEAP 이란?

힙

• 데이터 구조 유형
• 우선순위 대기열 구현에 널리 사용
• Max 및 Min 힙을 중심으로 다양한 유형

• 정의

* 힙은 힙 속성을 충족하는 특수한 트리 기반 데이터 구조
* 힙에서 특정 노드 I에 대해 I 값은 해당 하위 노드의 값보다 
  크거나 같거나 (최대 힙) 작거나 같음 (최소 힙)

* 각 노드에는 최대 2개의 하위 항목 (이진 힙)
* 왼쪽에서 오른쪽으로 채워지는 마지막 레벨을 제외하고 
  트리의 모든 레벨이 완전히 채워짐 (완전 이진 트리)

• 최대 힙

  • 루트의 키는 힙에 있는 모든 키 중에서 최대값
  • 힙은 삽입과 삭제 중에 루트가 항상 최대값을 가지도록 유지
    
    
  • 이진 트리의 모든 하위 트리에 대해 동일한 속성이 반복적으로 true
    
    
  • 용도
    • 최대 힙은 일반적으로 힙 정렬, k번째로 큰 요소 찾기 등과
      같은 알고리즘에 사용

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

    getParentIndex(i) { return Math.floor((i - 1) / 2); }
    getLeftChildIndex(i) { return 2 * i + 1; }
    getRightChildIndex(i) { return 2 * i + 2; }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    insert(key) {
        this.heap.push(key);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        let parentIndex = this.getParentIndex(index);

        while (index > 0 && this.heap[parentIndex] < this.heap[index]) {
            this.swap(parentIndex, index);
            index = parentIndex;
            parentIndex = this.getParentIndex(index);
        }
    }

    pop() {
        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.heapifyDown();
        return max;
    }

    heapifyDown(index = 0) {
        let largest = index;
        const heapSize = this.heap.length;

        while (true) {
            const leftChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);

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

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

            if (largest !== index) {
                this.swap(index, largest);
                index = largest;
            } else {
                break;
            }
        }
    }
}

• 최소 힙

  • 루트의 키는 힙에 있는 모든 키 중에서 최소값
  • 힙은 삽입과 삭제 중에 루트가 항상 최소값을 가지도록 유지
    
    
  • 이진 트리의 모든 하위 트리에 대해 동일한 속성이 반복적으로 true
    
    
  • 용도
    • Dijkstra의 최단 경로 알고리즘, Prim의 최소 스패닝 트리 알고리즘
      등과 같은 알고리즘에 사용

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

    getParentIndex(i) { return Math.floor((i - 1) / 2); }
    getLeftChildIndex(i) { return 2 * i + 1; }
    getRightChildIndex(i) { return 2 * i + 2; }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    insert(key) {
        this.heap.push(key);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        let parentIndex = this.getParentIndex(index);

        while (index > 0 && this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            index = parentIndex;
            parentIndex = this.getParentIndex(index);
        }
    }

    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.heapifyDown();
        return min;
    }

    heapifyDown(index = 0) {
        let smallest = index;
        const heapSize = this.heap.length;

        while (true) {
            const leftChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);

            if (leftChildIndex < heapSize && this.heap[leftChildIndex] < this.heap[smallest]) {
                smallest = leftChildIndex;
            }

            if (rightChildIndex < heapSize && this.heap[rightChildIndex] < this.heap[smallest]) {
                smallest = rightChildIndex;
            }

            if (smallest !== index) {
                this.swap(index, smallest);
                index = smallest;
            } else {
                break;
            }
        }
    }
}

• 다른 유형의 힙

  • 피보나치 힙
  • 이항 힙
  • 우선순위 큐

• 구현 방법

  • 배열로 구현
  • 삽입, 삭제, 힙파이와 같은 작업은 힙 구조를 유지하는 데 필수`