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

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)가 빠른 쪽이 우선적으로 나오도록 구현 가능