🧠 CS/자료구조

[자료구조] 우선순위 큐(priority queue)의 정렬 안정성

청월누리 2025. 4. 6. 15:48

C++ 표준 라이브러리인 std::priority_queue를 중심으로, 우선순위 큐가 정렬 안정성(stability)을 보장하지 않는 이유와 동작 방식을 정리한 글입니다.

우선순위 큐와 정렬 안정성

우선순위 큐 (priority queue)

  • 우선순위 큐는 가장 높은 우선 순위를 갖는 원소를 가장 먼저 꺼낼 수 있도록 하는 자료구조
  • C++ 표준 라이브러리에서는 std::priority_queue 템플릿 클래스로 제공 (<queue> 라이브러리 필요)
  • 내부적으로는 힙(heap)을 이용해 구현되어 있음

우선순위 큐 기본 코드

#include <queue>

// 기본 예시
std::priority_queue<int> pq;
pq.push(3);
pq.push(10);
pq.push(5);

// top() = 10   (가장 큰 값)
pq.pop();      // 10 제거
// top() = 5

정렬 안정성(stability)

  • 정렬 안정성이란, 값(혹은 우선순위)이 동일한 원소들 사이에서 정렬 전의 원래 순서(삽입 순서)를 유지하는 성질을 의미
  • 대표적으로 std::stable_sort는 동등 비교 결과를 얻는 원소들의 상대 순서를 바꾸지 않도록 보장
  • std::priority_queue를 비롯한 힙 기반 자료구조 전반은 정렬 안정성을 보장하지 않음

C++ std::priority_queue의 내부 동작과 힙(heap)

힙 기반 구현

  • std::priority_queue는 내부적으로 힙 자료구조를 사용
  • 힙은 완전 이진 트리 형태로, 노드(원소) 사이의 부모-자식 관계가 우선순위 비교로 정해짐
    • 최대 힙 (max-heap) : 부모 노드 값이 자식 노드의 값보다 항상 크거나 같도록 유지 ➡️ 우선순위 큐 기본 설정
    • 최소 힙 (min-heap) : 부모 노드 값이 자식 노드의 값보다 항상 작거나 같도록 유지 ➡️ C++에서 제공하지는 않지만, std::priority_queue<int, vector<int>, greater<int>> 형태로 만들어서 사용 가능 

출처 : https://guides.codepath.com/compsci/Heaps

힙 연산

  • push : 새로운 원소를 힙에 삽입 ➡️ 내부적으로 push_heap 알고리즘 사용
  • pop : 힙에서 가장 우선순위가 큰(또는 작은) 원소를 제거 ➡️ 내부적으로 pop_heap 알고리즘 사용

Max Heap에서 Push 연산 수행 과정
Max Heap에서 Pop 연산 수행 과정

✅ 힙 연산은 완전 이진 트리를 유지하면서 부모 - 자식 우선순위 관계가 위배되지 않도록 필요한 노드 교환(swap)이 이루어짐

✅ 이 과정에서 동등한 우선순위를 가진 원소들 사이의 상대적 순서는 고려되지 않음

정렬 안정성이 없는 이유

동등 우선순위 원소 처리

힙은 값(우선순위)이 동일한 원소를 대상으로 누가 먼저 들어왔는가를 추적할 필요도, 유지할 필요도 없다.

  • 내부적으로 힙을 구성할 때, 동등 우선순위는 트리 상에서 부모-자식 관계를 정하는 명확한 기준이 없으므로, 삽입 과정에서 임의의 위치에 들어갈 수 있음
  • 재조정(sift-up / sift-down)을 거치면서 동등 우선순위 원소들이 어떤 순서로 힙의 상단(루트)에 오르거나 내려가는지가 결정
  • 즉, 삽입 순서와 힙 상에서의 위치는 직결되지 않으며, 순서가 뒤섞일 수 있음

표준 라이브러리의 "엄격 약순서"

C++에서 커스텀 정렬을 위해 사용하는 비교 연산(ex. bool operator<(const T& right))는 보통 엄격 약순서(strict weak ordering)를 만족해야 한다.

  • a < a가 성립되지 않아야 한다 & 비교가 순환되지 않아야 한다 & 등등 의 조건이 필요
  • 값이 같으면 (우선순위가 같으면) 비교 결과는 false 라는 형태로 구현되는 경우가 많음

✅ 동등한(우선순위가 동일한) 요소들은 어느 한쪽이 작거나 큰 것으로 간주되지 않기 때문에 힙 정렬 관점에서 우선순위가 동일 ➡️ 서로 교환이 이루어질 수도 있고, 이루어지지 않을 수도 있음 (컴파일러 최적화 또는 내부 구현에 따라 달라짐) ➡️ 입력 순서를 유지할 이유가 사라지므로 최종 pop 연산을 수행하는 과정에서 동일 우선순위 요소의 순서는 재멋대로가 됨

불안정성에 대한 코드 예시

#include <iostream>
#include <queue>
using namespace std;

struct Data {
    int value;  // 우선순위
    int index;  // 삽입 순서 추적

    bool operator<(const Data& other) const {
        // (최대 힙) value가 클수록 우선순위가 높다
        // 둘의 value가 같으면 비교 결과 false → "동등"
        if (value > other.value) return true;
        if (value < other.value) return false;
        return false; 
    }
};

int main() {
    priority_queue<Data> pq;

    // 모두 'value=10'으로 동일하지만, index는 0부터 4까지로 다름
    for (int i = 0; i < 5; i++) {
        pq.push({10, i});
        cout << "Pushed : value=10, index=" << i << endl;
    }

    cout << "---------- Pop Sequence ----------\n";
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        cout << "Popped : value=" << top.value 
             << ", index=" << top.index << endl;
    }
    return 0;
}

  • 모든 요소가 value = 10으로 동일(동등한 우선순위)하기 때문에 priority_queue는 index 순서(입력 순서)를 고려하지 않음

정렬 안정성이 필요한 경우 해결 방법

일반적으로 우선순위 큐를 사용할 때, 우선순위(값)의 대소 관계만 중요하다면 정렬 안정성은 고려하지 않아도 상관 없다.

  • 동일 우선순위의 요소가 여러 개 있고, 이를 입력된 순서대로 처리해야 하는 경우 ➡️ 정렬 안정싱 중요
  • 동등 비교 결과가 잦게 발생하고, 처리 순서가 결과가 영향을 미치는 경우 ➡️ 정렬 안정성 중요

✅ 정렬 안정성이 필요한 경우, 추가 필드(고유 ID 등)를 사용하여 동등 우선순위에서도 순서를 비교할 수 있도록 구현하거나 안정 정렬을 지원하는 구조를 직접 만들어서 사용

✅ 구조체에 id 필드를 추가하여 데이터를 삽입할 때마다 증가시킨 후, 비교 합수에 return id  < right.id;를 추가하면, 우선순위가 높은 것끼리 먼저 나오되, 동등 우선순위의 경우 삽입 순서(id)가 빠른 쪽이 우선적으로 나오도록 구현 가능