[자료구조] C++로 이중 우선순위 큐 구현 - 3. 이중 우선순위 큐

두 힙만 합치면 안 되는 이유

최소 힙은 최솟값을, 최대 힙은 최댓값을 루트에서 바로 찾습니다. 같은 값을 두 힙에 모두 넣으면 삽입과 양 끝 조회까지는 간단하지만, 한쪽에서 삭제한 원소가 다른 쪽에도 남는 동기화 문제가 생깁니다.

유효한 값: 10, 20, 30
minHeap.top(): 10
maxHeap.top(): 30

popMin() 실행
→ 최소 힙의 10은 루트라서 바로 삭제 가능
→ 최대 힙의 10은 중간에 있어 바로 찾기 어려움

이진 힙은 루트 삽입·삭제가 아니라 루트 조회와 끝 삽입, 루트 삭제에 최적화된 구조입니다. 중간 원소의 위치를 알 수 없으므로 다른 힙에서 같은 원소를 찾고 삭제하면 최악의 경우 O(N)이 걸립니다.

지연 삭제로 두 힙 동기화하기

다른 힙의 중간 원소를 즉시 찾는 대신, 삭제된 원소라는 사실만 기록해 둡니다. 그 원소가 나중에 루트까지 올라왔을 때 실제로 버리는 방식을 지연 삭제(lazy deletion)라고 합니다.

1. 삭제하려는 쪽의 루트가 이미 무효라면 계속 pop()한다.
2. 유효한 루트를 찾으면 그 원소의 유효 상태를 제거한다.
3. 반대쪽 힙에 남은 복사본은 당장 건드리지 않는다.
4. 그 복사본이 반대쪽 루트가 되는 시점에 정리한다.

연산	논리적으로 유효한 값	실제 정리
I 10, I 20, I 30	10, 20, 30	두 힙에 모두 삽입
D -1	20, 30	최소 힙의 10만 즉시 제거
D 1	20	최대 힙의 30 제거, 10은 아직 남을 수 있음
최댓값 조회	20	루트에 도달한 무효 원소를 먼저 제거

고유 ID와 값별 개수 중 무엇을 기록할까?

가장 일반적인 방법은 삽입할 때마다 고유 ID를 붙여 두 힙에 (value, id)를 저장하고, valid[id]로 각 원소의 생존 여부를 관리하는 것입니다. 삽입 순서처럼 같은 값의 개별 원소를 구분해야 한다면 이 방식이 필요합니다.

minHeap.push({value, id});
maxHeap.push({value, id});
valid[id] = true;

이번 큐는 같은 값끼리 구분할 필요가 없습니다. 5, 5, 5 중 어느 5가 삭제되어도 결과가 같기 때문에, unordered_map<int, int>에 값별 유효 개수만 기록할 수 있습니다.

counts[value]++;  // 삽입
counts[value]--;  // 최소 또는 최대 원소 하나 삭제

counts는 힙 내부에 그 값이 몇 개 저장되어 있는지가 아니라, 현재 큐에서 논리적으로 살아 있는 개수입니다. 힙에 남은 개수가 더 많다면 그 차이가 아직 물리적으로 제거되지 않은 낡은 원소입니다.

삽입과 삭제 연산의 흐름

• 삽입 I value
• 값을 두 힙에 모두 넣고 counts[value]와 전체 유효 개수를 1씩 늘립니다.
• 최솟값 삭제 D -1
• 최소 힙의 무효 루트를 정리한 뒤 유효한 루트를 제거하고 그 값의 개수를 1 줄입니다.
• 최댓값 삭제 D 1
• 최대 힙에서도 같은 순서로 무효 루트를 정리한 뒤 유효한 최댓값 하나를 제거합니다.
• 최종 조회
• 두 힙을 각각 한 번 더 정리한 뒤 최소 힙과 최대 힙의 루트를 읽습니다.

빈 큐에서 삭제 명령이 들어오면 무시합니다. 반면 min()과 max()는 반환할 값이 없으므로 예외를 던지도록 계약을 분명히 했습니다.

최종 구현

#include "MaxHeap.h"
#include "MinHeap.h"

#include <iostream>
#include <stdexcept>
#include <unordered_map>

class DualPriorityQueue {
private:
    MinHeap minHeap;
    MaxHeap maxHeap;

    // 큐에서 논리적으로 살아 있는 값별 개수
    std::unordered_map<int, int> counts;
    int activeSize = 0;

    void cleanMinHeap() {
        while (!minHeap.empty()) {
            int value = minHeap.top();
            auto it = counts.find(value);

            if (it != counts.end() && it->second > 0) {
                break;
            }

            minHeap.pop();
        }
    }

    void cleanMaxHeap() {
        while (!maxHeap.empty()) {
            int value = maxHeap.top();
            auto it = counts.find(value);

            if (it != counts.end() && it->second > 0) {
                break;
            }

            maxHeap.pop();
        }
    }

    void removeCount(int value) {
        auto it = counts.find(value);

        if (it == counts.end()) {
            return;
        }

        if (--it->second == 0) {
            counts.erase(it);
        }

        --activeSize;
    }

public:
    void push(int value) {
        minHeap.push(value);
        maxHeap.push(value);
        ++counts[value];
        ++activeSize;
    }

    void popMin() {
        if (empty()) {
            return;
        }

        cleanMinHeap();
        int value = minHeap.top();
        minHeap.pop();
        removeCount(value);
    }

    void popMax() {
        if (empty()) {
            return;
        }

        cleanMaxHeap();
        int value = maxHeap.top();
        maxHeap.pop();
        removeCount(value);
    }

    int min() {
        if (empty()) {
            throw std::runtime_error("Queue is empty");
        }

        cleanMinHeap();
        return minHeap.top();
    }

    int max() {
        if (empty()) {
            throw std::runtime_error("Queue is empty");
        }

        cleanMaxHeap();
        return maxHeap.top();
    }

    bool empty() const {
        return activeSize == 0;
    }

    int size() const {
        return activeSize;
    }
};

int main() {
    DualPriorityQueue queue;

    queue.push(30);
    queue.push(10);
    queue.push(20);

    std::cout << "Min: " << queue.min() << '\n';
    std::cout << "Max: " << queue.max() << '\n';

    queue.popMin();
    queue.popMax();

    std::cout << "Remaining: " << queue.min() << '\n';

    queue.popMin();
    std::cout << std::boolalpha
              << "Queue empty: " << queue.empty()
              << '\n';
}

이 구현은 앞선 두 글의 MinHeap과 MaxHeap이 push, pop, top, empty를 제공한다는 전제입니다. 프로그래머스 형식의 I n, D 1, D -1 문자열은 파싱한 뒤 각각 push(n), popMax(), popMin()에 연결하면 됩니다.

시간 복잡도와 분할 상환 분석

연산	시간 복잡도	이유
삽입	O(log N)	두 힙에 삽입
최솟값 삭제	O(log N) 분할 상환	최소 힙 삭제와 무효 원소 정리
최댓값 삭제	O(log N) 분할 상환	최대 힙 삭제와 무효 원소 정리
최솟값/최댓값 조회	O(log N) 분할 상환	루트 조회 전 무효 원소 정리 가능
논리적 크기 확인	O(1)	activeSize 조회

 

한 번의 정리에서 여러 낡은 원소가 연속으로 빠지면 그 연산만 보면 O(N log N)처럼 보일 수 있습니다. 하지만 각 복사본은 힙에 한 번 삽입되고 최대 한 번 제거됩니다. 여러 연산에 걸친 전체 정리 비용이 제한되므로 연산당 비용은 분할 상환 기준 O(log N)입니다.

두 힙에는 아직 정리되지 않은 복사본이 남을 수 있어 물리적 저장 공간은 현재 activeSize보다 큽니다. 그래도 삽입된 원소마다 두 복사본만 만들기 때문에 전체 공간 복잡도는 O(N)입니다.

정리

• 최소 힙과 최대 힙을 함께 쓰면 양 끝값을 빠르게 찾을 수 있다.
• 한쪽 힙의 중간 원소를 즉시 지우지 않고 무효 상태만 기록한다.
• 무효 원소가 루트에 도달했을 때 제거하는 방식을 지연 삭제라고 한다.
• 같은 값을 개별적으로 구분할 필요가 없다면 고유 ID 대신 값별 유효 개수를 사용할 수 있다.
• 각 낡은 원소는 최대 한 번 정리되므로 삽입과 양 끝 삭제는 분할 상환 O(log N)이다.

이번 구현으로 힙 3부작을 마쳤습니다. 최소 힙과 최대 힙의 개별 동작에서 한 걸음 더 나아가, 각 자료구조가 잘하는 연산은 유지하면서 동기화 비용을 별도의 상태와 지연 처리로 해결하는 방법을 확인했습니다.