[C++로 배우는 알고리즘과 자료구조] Day 9: 힙과 우선순위 큐

힙 (Heap)

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

힙의 종류:

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

우선순위 큐 (Priority Queue)

우선순위 큐는 힙을 기반으로 구현되며, 각 요소가 우선순위를 가지는 큐입니다. 우선순위 큐는 삽입과 삭제 연산에서 우선순위에 따라 요소를 정렬합니다. 따라서 가장 높은 우선순위를 가진 요소를 O(log n) 시간 복잡도로 삽입하거나 삭제할 수 있습니다.

힙 구현

힙의 기본 연산:

1. 삽입 (Insert): 새로운 요소를 힙에 삽입합니다.
2. 삭제 (Remove): 루트 요소를 삭제합니다.
3. 힙 구성 (Heapify): 힙의 속성을 유지하도록 트리를 구성합니다.

최대 힙 구현 예제

MaxHeap.h

#ifndef MAXHEAP_H
#define MAXHEAP_H

#include <vector>
#include <iostream>

class MaxHeap {
public:
    MaxHeap() {}

    void insert(int value); // 요소 삽입
    void remove(); // 루트 요소 삭제
    int getMax() const; // 최대값 반환
    void display() const; // 힙 요소 출력

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;
}

#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(); // 루트 삭제 후 힙 요소 출력

    return 0;
}

 

우선순위 큐 구현

PriorityQueue.h

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H

#include "MaxHeap.h"

class PriorityQueue {
public:
    void push(int value) {
        maxHeap.insert(value); // 요소 삽입
    }

    void pop() {
        maxHeap.remove(); // 루트 요소 삭제
    }

    int top() const {
        return maxHeap.getMax(); // 최대값 반환
    }

    bool isEmpty() const {
        return maxHeap.empty(); // 우선순위 큐가 비어 있는지 확인
    }

    void display() const {
        maxHeap.display(); // 힙 요소 출력
    }

private:
    MaxHeap maxHeap; // 최대 힙
};

#endif // PRIORITYQUEUE_H

 

우선순위 큐 예제

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

int main() {
    PriorityQueue pq;
    pq.push(10);
    pq.push(20);
    pq.push(15);
    pq.push(30);
    pq.push(40);

    std::cout << "우선순위 큐 요소: ";
    pq.display(); // 우선순위 큐 요소 출력

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

    pq.pop();
    std::cout << "루트 삭제 후 우선순위 큐 요소: ";
    pq.display(); // 루트 삭제 후 우선순위 큐 요소 출력

    return 0;
}

 

설명

1. 힙 (Heap):
   • 힙은 완전 이진 트리 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다.
   • 최대 힙(Max-Heap)은 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
   • 최소 힙(Min-Heap)은 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
2. 힙의 주요 연산:
   • 삽입 (Insert): 새로운 요소를 힙에 삽입합니다.
   • 삭제 (Remove): 루트 요소를 삭제합니다.
   • 힙 구성 (Heapify): 힙의 속성을 유지하도록 트리를 구성합니다.
3. 우선순위 큐 (Priority Queue):
   • 우선순위 큐는 힙을 기반으로 구현되며, 각 요소가 우선순위를 가지는 큐입니다.
   • 우선순위 큐의 주요 연산은 push, pop, top, isEmpty입니다.

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

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 10: 트라이 (Trie)"에 대해 학습하겠습니다.