[자료구조] 힙 heap

heap은 우선순위 큐를 위한 자료구조
최댓값과 최솟값을 빠르게 찾기 위해서 만들어진 자료형
일반적으로 노드가 왼쪽부터 채워지는 완전 이진 트리

힙을 사용하면 최댓값과 최솟값을 찾는데 시간 복잡도가 낮음
힙을 사용하면 O(logn) 만큼 소요
정렬을 사용하게 되면 O(n)만큼의 시간 복잡도

• 최대 힙(max heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

• 최소 힙(min heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

데이터 삽입

완전 이진 트리이므로 왼쪽 노드부터 채워진다.
새롭게 채워지는 데이터가 부모보다 작으면 순서대로 채워진다.

다만, 새로 채워지는 데이터가 부모보다 크면 swap이 발생한다.

우선 채워진 후에, 부모 노드보다 클 경우 swap 연산을 통해 자리를 바꾼다.

20이 8과 자리를 바꿔도 20의 부모인 15보다 크므로 또 자리를 바꿔야한다.

데이터 삭제

힙의 목표는 최댓값이나 최솟값을 알아내는 것
따라서 루트 노드가 삭제됨

가장 하단의 노드가 루트 노드로 올라오고, 왼쪽 오른쪽 자식 노드과 비교한 후에 루트 노드보다 큰 노드랑 자리를 바꾼다.
다만, 사진과 같이 두개의 자식 노드가 둘 다 크다면 더 큰 노드와 자리를 바꾼다.

c++ 코드 구현

#include <iostream>
#include <vector>
#include <stdexcept>

class MinHeap {
private:
    std::vector<int> heap;

    // 부모 노드의 인덱스 계산
    int parent(int index) { return (index - 1) / 2; }
    // 왼쪽 자식 노드의 인덱스 계산
    int leftChild(int index) { return 2 * index + 1; }
    // 오른쪽 자식 노드의 인덱스 계산
    int rightChild(int index) { return 2 * index + 2; }

    // 힙 성질 유지: 삽입 시 위로 이동
    void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] > heap[index]) {
            std::swap(heap[parent(index)], heap[index]);
            index = parent(index);
        }
    }

    // 힙 성질 유지: 삭제 시 아래로 이동
    void heapifyDown(int index) {
        int smallest = index;
        int left = leftChild(index);
        int right = rightChild(index);

        if (left < heap.size() && heap[left] < heap[smallest])
            smallest = left;
        if (right < heap.size() && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != index) {
            std::swap(heap[index], heap[smallest]);
            heapifyDown(smallest);
        }
    }

public:
    // 힙에 요소 삽입
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    // 최소값 제거 및 반환
    int extractMin() {
        if (heap.empty()) {
            throw std::out_of_range("Heap is empty");
        }

        int minValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return minValue;
    }

    // 힙의 최소값 확인
    int getMin() {
        if (heap.empty()) {
            throw std::out_of_range("Heap is empty");
        }
        return heap[0];
    }

    // 힙의 요소 출력 (디버깅용)
    void printHeap() {
        for (int value : heap) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    MinHeap heap;

    heap.insert(10);
    heap.insert(20);
    heap.insert(5);
    heap.insert(15);

    std::cout << "Heap elements: ";
    heap.printHeap();

    std::cout << "Minimum value: " << heap.getMin() << std::endl;

    std::cout << "Extracting min: " << heap.extractMin() << std::endl;
    heap.printHeap();

    return 0;
}