[c++] 최소 힙(Min Heap) 구현

12 Dec 2023

먼저, 최소 힙을 나타내는 MinHeap 클래스를 선언하고 구현해 보겠습니다.

#include <iostream>
#include <vector>

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

    void heapifyUp(int index) {
        if (index && heap[index] < heap[(index - 1) / 2]) {
            std::swap(heap[index], heap[(index - 1) / 2]);
            heapifyUp((index - 1) / 2);
        }
    }

    void heapifyDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        if (left < heap.size() && heap[left] < heap[index]) {
            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 key) {
        heap.push_back(key);
        int index = heap.size() - 1;
        heapifyUp(index);
    }

    void deleteKey(int key) {
        int index;
        for (index = 0; index < heap.size(); index++) {
            if (key == heap[index]) break;
        }
        if (index == heap.size()) return;
        std::swap(heap[index], heap.back());
        heap.pop_back();
        heapifyDown(index);
    }

    int getMin() {
        if (heap.size()) {
            return heap.front();
        }
        return -1;
    }
};

위의 코드에서는 MinHeap 클래스를 작성했습니다. 클래스에는 private 벡터 heap과 heapifyUp, heapifyDown, insert, deleteKey, getMin 메서드가 있습니다. heapifyUp 및 heapifyDown 메서드는 힙 속성을 유지하기 위해 사용됩니다. insert, deleteKey 및 getMin 메서드는 각각 삽입, 삭제 및 최소값 검색을 담당합니다.

이제 MinHeap 클래스를 사용하여 최소 힙을 테스트할 수 있습니다. 아래의 예시는 MinHeap 클래스를 사용하여 최소 힙을 구성하고 작동시키는 방법을 보여줍니다.

int main() {
    MinHeap minHeap;
    
    minHeap.insert(10);
    minHeap.insert(30);
    minHeap.insert(20);
    minHeap.insert(40);

    std::cout << "Min element: " << minHeap.getMin() << std::endl;

    minHeap.deleteKey(20);

    std::cout << "Min element after deleting 20: " << minHeap.getMin() << std::endl;

    return 0;
}