[C++로 배우는 알고리즘과 자료구조] Day 13: 이진 힙과 힙 정렬

이진 힙 (Binary Heap)

이진 힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다. 이진 힙은 주로 최대값이나 최소값을 빠르게 찾기 위해 사용됩니다. 이진 힙에는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있습니다.

이진 힙의 종류:

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

힙 정렬 (Heap Sort)

힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.

힙 정렬의 과정:

1. 배열을 이진 힙으로 변환합니다.
2. 힙의 루트 요소를 제거하고, 힙을 재구성하여 정렬된 배열을 만듭니다.

최대 힙 구현

MaxHeap.h

#ifndef MAXHEAP_H
#define MAXHEAP_H

#include <vector>
#include <algorithm>
#include <iostream>

class MaxHeap {
public:
    MaxHeap() {}

    void insert(int value); // 요소 삽입
    void remove(); // 루트 요소 삭제
    int getMax() const; // 최대값 반환
    void display() const; // 힙 요소 출력
    void heapify(std::vector<int>& arr, int n, int i); // 힙 속성 유지
    void heapSort(std::vector<int>& arr); // 힙 정렬

private:
    std::vector<int> heap; // 힙을 저장하는 벡터

    void heapifyUp(int index); // 힙 속성 유지 (삽입 시 위로 이동)
    void heapifyDown(int index); // 힙 속성 유지 (삭제 시 아래로 이동)
};

// 요소 삽입 함수 정의
void MaxHeap::insert(int value) {
    heap.push_back(value); // 힙의 끝에 요소 삽입
    heapifyUp(heap.size() - 1); // 힙 속성 유지
}

// 힙 속성 유지 함수 정의 (삽입 시 위로 이동)
void MaxHeap::heapifyUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index] <= heap[parent]) {
            break; // 힙 속성을 만족하면 종료
        }
        std::swap(heap[index], heap[parent]); // 부모와 자식 요소 교환
        index = parent; // 인덱스를 부모로 이동
    }
}

// 루트 요소 삭제 함수 정의
void MaxHeap::remove() {
    if (heap.empty()) {
        throw std::runtime_error("Heap is empty");
    }
    heap[0] = heap.back(); // 마지막 요소를 루트로 이동
    heap.pop_back(); // 마지막 요소 삭제
    heapifyDown(0); // 힙 속성 유지
}

// 힙 속성 유지 함수 정의 (삭제 시 아래로 이동)
void MaxHeap::heapifyDown(int index) {
    int size = heap.size();
    while (index < size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left < size && heap[left] > heap[largest]) {
            largest = left; // 왼쪽 자식이 더 큰 경우
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right; // 오른쪽 자식이 더 큰 경우
        }
        if (largest == index) {
            break; // 힙 속성을 만족하면 종료
        }
        std::swap(heap[index], heap[largest]); // 부모와 자식 요소 교환
        index = largest; // 인덱스를 자식으로 이동
    }
}

// 최대값 반환 함수 정의
int MaxHeap::getMax() const {
    if (heap.empty()) {
        throw std::runtime_error("Heap is empty");
    }
    return heap[0]; // 루트 요소 반환
}

// 힙 요소 출력 함수 정의
void MaxHeap::display() const {
    for (int value : heap) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
}

// 힙 속성 유지 함수 정의 (힙 정렬)
void MaxHeap::heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 힙 정렬 함수 정의
void MaxHeap::heapSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

#endif // MAXHEAP_H

 

최대 힙 및 힙 정렬 예제

#include <iostream>
#include "MaxHeap.h"

int main() {
    MaxHeap heap;
    heap.insert(10);
    heap.insert(20);
    heap.insert(15);
    heap.insert(30);
    heap.insert(40);

    std::cout << "힙 요소: ";
    heap.display(); // 힙 요소 출력

    std::cout << "최대값: " << heap.getMax() << std::endl; // 최대값 출력

    heap.remove();
    std::cout << "루트 삭제 후 힙 요소: ";
    heap.display(); // 루트 삭제 후 힙 요소 출력

    std::vector<int> arr = {4, 10, 3, 5, 1};
    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    heap.heapSort(arr);

    std::cout << "힙 정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

설명

1. 이진 힙 (Binary Heap):
   • 이진 힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다.
   • 최대 힙(Max-Heap)은 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
   • 최소 힙(Min-Heap)은 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
2. 힙 정렬 (Heap Sort):
   • 힙 정렬은 이진 힙을 이용한 정렬 알고리즘입니다.
   • 배열을 이진 힙으로 변환한 후, 힙의 루트 요소를 제거하고 힙을 재구성하여 정렬된 배열을 만듭니다.
   • 힙 정렬의 평균 및 최악의 경우 시간 복잡도는 (O(n \log n))입니다.

이제 이진 힙과 힙 정렬의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 14: 해시 함수와 충돌 해결 기법"에 대해 학습하겠습니다.