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 기준 내림차순 출력처럼 보입니다.
