우선순위 큐와 힙

우선순위 큐

 

데이터 요소들이 우선순위를 기준으로 정렬되어 처리되는 큐

 

FIFO(First In, First Out) 방식인 일반 큐와 달리 가장 높은 우선순위를 가진 요소가 먼저 처리된다.

 

특징

각 요소는 값과 우선순위를 가진다.

 

삽입은 어느 위치든 가능하지만, 삭제는 항상 우선순위가 가장 높은 요소부터 이루어진다.

 

사용 예시

 

작업 스케줄링: CPU 스케줄링에서 높은 우선순위의 작업을 먼저 실행한다.

 

네트워크 라우팅: 트래픽 처리에서 긴급한 패킷을 우선 처리한다.

힙

 

완전 이진 트리 형태의 자료구조로, 우선순위 큐를 효율적으로 구현하기 위해 사용한다.

 

힙은 두 가지 유형으로 나누어진다.

 

최대 힙: 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같음

 

최소 힙: 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같음

 

힙의 특징

 

완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워진다.

 

삽입/삭제/최대값 또는 최소값 조회 연산이 O(logN)으로 효율적이다.

 

구현 알고리즘

 

삽입: 새로운 노드를 트리의 가장 마지막에 추가한 후, 부모 노드와 비교하여 조건이 만족될 때까지 자리를 교환한다.

 

삭제: 루트 노드를 제거한 뒤, 가장 마지막 노드를 루트로 옮기고 자식 노드와 비교하여 조건을 만족할 때까지 자리를 교환한다.

 

소스코드

#include <iostream>
#include <vector>

class MaxHeap {
private:
    std::vector<int> heap; // 힙을 저장하는 배열 기반 자료구조

    // 힙 위로 정렬: 새로 추가된 요소를 부모와 비교하며 이동
    void heapify_up(int index) {
        int parent = (index - 1) / 2; // 부모 노드 인덱스
        if (index > 0 && heap[index] > heap[parent]) {
            std::swap(heap[index], heap[parent]); // 부모와 교환
            heapify_up(parent); // 재귀적으로 부모 노드 처리
        }
    }

    // 힙 아래로 정렬: 루트 요소를 자식과 비교하며 이동
    void heapify_down(int index) {
        int left = 2 * index + 1;  // 왼쪽 자식 인덱스
        int right = 2 * index + 2; // 오른쪽 자식 인덱스
        int largest = index;       // 현재 노드가 가장 큰 값이라고 가정

        if (left < heap.size() && heap[left] > heap[largest])
            largest = left; // 왼쪽 자식이 더 크면 largest 갱신
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right; // 오른쪽 자식이 더 크면 largest 갱신

        if (largest != index) {
            std::swap(heap[index], heap[largest]); // 가장 큰 자식과 교환
            heapify_down(largest); // 재귀적으로 자식 노드 처리
        }
    }

public:
    // 힙에 값 추가
    void push(int value) {
        heap.push_back(value);      // 배열 끝에 추가
        heapify_up(heap.size() - 1); // 힙 위로 정렬
    }

    // 힙의 루트 값 제거
    void pop() {
        if (heap.empty()) {
            std::cerr << "Heap is empty!" << std::endl;
            return;
        }
        heap[0] = heap.back();      // 마지막 요소를 루트로 이동
        heap.pop_back();            // 마지막 요소 제거
        heapify_down(0);            // 힙 아래로 정렬
    }

    // 힙의 루트 값 반환
    int top() const {
        if (!heap.empty())
            return heap[0];
        throw std::runtime_error("Heap is empty!"); // 힙이 비었을 때 예외 처리
    }

    // 힙이 비었는지 확인
    bool empty() const {
        return heap.empty();
    }

    // 힙 내용 출력
    void print() const {
        for (int value : heap)
            std::cout << value << " ";
        std::cout << std::endl;
    }
};

int main() {
    MaxHeap heap;

    // 힙에 값 추가
    heap.push(10);
    heap.push(20);
    heap.push(5);
    heap.push(15);
    heap.push(30);

    std::cout << "Max-Heap 내용: ";
    heap.print();

    // 루트 값 확인
    std::cout << "힙의 루트 값: " << heap.top() << std::endl;

    // 루트 값 제거
    heap.pop();
    std::cout << "루트 제거 후 Max-Heap: ";
    heap.print();

    return 0;
}

우선순위 큐와 힙의 관계

 

힙은 우선순위 큐를 구현하기 위한 대표적인 자료구조이다.

 

우선순위 큐를 힙으로 구현하면 삽입/삭제 시 시간 복잡도 O(logN)을 보장한다.

 

완전 이진 트리랑 힙의 차이점

 

힙은 완전 이진 트리를 기반으로 하면서 추가적인 조건인 힙 속성을 만족하는 자료구조이다.