BinaryHeap을 이용해 내림차순으로 정렬하기

BinaryHeap은 가장 큰 값을 맨 앞에 위치시키고, 나머지 값들은 임의의 순서대로 저정하지만, pop()을 사용하면 내림차순으로 정렬한 것처럼 보이게 할 수 있습니다.

1. 코드

use std::collections::BinaryHeap;

fn main() {
    let mut jobs = BinaryHeap::new();

    jobs.push((100, "Write back to email from the CEO"));
    jobs.push((80, "Finish the report today"));
    jobs.push((5, "Watch Some YouTube"));
    jobs.push((70, "Tell your team members thanks for always working hand"));
    jobs.push((30, "Plan who to hire next for the team"));

    while let Some(job) = jobs.pop() {
        println!("You need to: {}", job.1)
    }
}

위 코드를 실행하면 아래와 같이 중요한 일부터, 다시 말해 jobs의 첫번째 항목 점수를 기준으로 내림차순으로 정렬됩니다.

2. BinaryHeap의 기본 비교 규칙

BinaryHeap은 내부적으로 T: Ord 트레이트를 요구합니다.
즉, 요소 T 간의 대소 비교(>, <)가 가능해야 하죠.

Rust에서 tuple(예: (i32, &str))도 기본적으로 Ord를 구현하고 있으며, 사전식(lexicographical) 비교를 합니다.

(a₁, b₁) < (a₂, b₂)
⟹ a₁ < a₂ 이면 그걸로 비교 종료,
⟹ a₁ == a₂ 이면 b₁과 b₂를 비교함.

즉,
(100, “CEO”)와 (80, “report”)를 비교할 때
→ 100 > 80이므로 (100, “CEO”)가 “더 큰” 값으로 간주됩니다.

이 때문에 BinaryHeap은 자동으로 첫 번째 원소(i32) 를 기준으로 최대 힙을 구성합니다.

3. “맨 위(root)”만 정렬되어 있는 이유

BinaryHeap은 완전이진트리(Complete Binary Tree) 구조로 되어 있습니다.

힙은 전체가 정렬되어 있지는 않습니다.
단지 루트 노드(맨 위) 가 항상 가장 큰 값입니다.
나머지는 “힙 속성(heap property)”만 유지합니다: 부모 ≥ 자식

그래서 jobs.pop()을 반복할 때마다

매번 가장 큰 (i32, &str) 튜플이 하나씩 빠집니다.
내부적으로 남은 값들이 재배열되어 다시 최대 힙이 됩니다.

결과적으로, pop()을 반복하면 내림차순 정렬된 순서로 출력되는 것처럼 보이는 거예요.

4. 즉, “항상 정렬되어 있는 게 아니라”

BinaryHeap의 내부 저장순서는 무작위입니다.
하지만 pop()할 때마다 가장 큰 값이 나오는 이유는
“루트만 최대값이 되도록 하는 BinaryHeap 속성” 때문입니다.

5. 정리

개념	의미
내부 저장 순서	무작위 (정렬 아님)
비교 기준	Ord 구현(튜플이면 첫 번째 요소부터 비교)
pop()동작	항상 최대값 반환
출력 결과	내림차순처럼 보임 (사실은 매번 루트 제거 과정 때문)

6. 오름차순 정렬

만약 작은 값부터 꺼내고 싶다면, 즉 “최소 힙(min-heap)”을 원한다면 이렇게 하면 됩니다:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut jobs = BinaryHeap::new();

    jobs.push(Reverse((100, "CEO")));
    jobs.push(Reverse((80, "Report")));
    jobs.push(Reverse((5, "YouTube")));

    while let Some(Reverse(job)) = jobs.pop() {
        println!("You need to: {}", job.1);
    }
}

이렇게 하면 작은 i32부터 오름차순으로 출력됩니다.

요약하자면 👇

BinaryHeap은 내부가 정렬된 컬렉션이 아니라, 루트에만 최대값을 유지하는 자료구조이고,
(i32, &str) 튜플은 기본적으로 첫 번째 값으로 비교되기 때문에,
pop()을 반복하면 결과적으로 i32 기준 내림차순 출력처럼 보입니다.