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) 비교를 합니다.
즉, (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 기준 내림차순 출력처럼 보입니다.
Rust에서 array와 vector는 모두 여러 개의 값을 순차적으로 저장하는 자료구조입니다. 하지만 두 타입은 메모리 관리, 크기, 사용 목적 등에서 중요한 차이점이 있습니다. 이 글에서는 각 자료구조의 특징, 사용법, 예제, 그리고 언제 어떤 것을 선택해야 하는지에 대해 자세히 알아보겠습니다.
let slice = &v[1..3]; println!(“{:?}”, slice); => v 벡터에서 1번 인덱스부터 3미만인 2번 인덱스까지 참조 형식으로 가져오는 slice는 [99, 3]이 됩니다. Vector는 일반 포맷인 {}로는 출력이 안되므로 디버그 포맷인 {:?}으로 출력해야 합니다.
let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect(); println!(“{:?}”, doubled); => v 벡터의 요소 들에 2를 곱한 후 새로운 벡터로 변환한 후 doubled에 저장합니다. doubled의 타입도 i32타입의 Vector이므로 디버그 포맷으로 출력하면 [2, 198, 6, 8, 10, 12, 14, 16, 18]가 출력됩니다.
6. 성능 차이의 실제 사례
6.1. 반복문에서의 성능
fn main() { let arr = [1; 1000000]; let vec = vec![1; 1000000];
let mut sum = 0; for i in 0..arr.len() { sum += arr[i]; }
let mut sum2 = 0; for i in 0..vec.len() { sum2 += vec[i]; } }
실행 시간: 배열이 벡터보다 약간 더 빠른 경우가 많습니다.
이유: 배열은 스택에 연속적으로 저장되어 CPU 캐시 효율이 높고, 컴파일러가 최적화를 더 적극적으로 적용할 수 있습니다.
위와 같이 배열의 개수를 1백만개로 숫자가 1인데도 array의 경우 overflow가 발생하므로 1십만으로 바꾸는데, 시간을 체크하는 부분을 추가하고, 천단위 쉼표를 추가하도록 아래와 같이 수정한 후
[Cargo.toml] -num-format 크레이트를 사용하기 위해 필요
[dependencies] num-format = "0.4"
[main.rs]
use std::time::Instant; use num_format::{Locale, ToFormattedString};
fn main() { let arr = [1; 100_000]; let vec = vec![1; 100_000];
// 배열 합계 시간 측정 let start = Instant::now(); let mut sum = 0; for i in 0..arr.len() { sum += arr[i]; } let duration = start.elapsed(); println!("Array sum: {}, elapsed: {:?}", sum.to_formatted_string(&Locale::ko), duration);
// 벡터 합계 시간 측정 let start = Instant::now(); let mut sum2 = 0; for i in 0..vec.len() { sum2 += vec[i]; } let duration = start.elapsed(); println!("Vector sum: {}, elapsed: {:?}", sum2.to_formatted_string(&Locale::ko), duration); }
Instant::now()로 현재 시각을 기록하고, 반복문이 끝난 후 elapsed()로 소요 시간을 구합니다.
for i in 0..arr.len()라고 0부터 배열의 길이전까지 i를 반복하면 sum에 arr[i]를 더하도록 했는데, for i in arr.iter()라고 하고, sum += i;이라고 해도 되는데, iter()를 이용한 것이 훨씬 빠릅니다. 특히 Vector 속도가 많이 빨라졌습니다. Array sum: 100,000, elapsed: 728.6µs Vector sum: 100,000, elapsed: 875.7µs ※ 그런데 매번 속도가 다르기 때문에 위 수치가 절대적인 것은 아닙니다. 어느 때는 Vector가 빠른 경우도 있습니다.
sum 또는 sum2 다음에 num_format의 ToFormattedString(&Locale::ko)를 추가해서 숫자에 천단위마다 쉼표를 추가합니다.
6.2. 크기 변경 및 데이터 추가
배열은 크기가 고정되어 있어, 데이터 추가/삭제가 불가능합니다.
벡터는 push, pop, extend 등으로 동적으로 크기를 조절할 수 있지만, 이 과정에서 메모리 재할당이 발생할 수 있습니다. 대량의 데이터를 추가할 때는 재할당 오버헤드가 성능 저하 요인이 됩니다.
6.3. 벤치마크 및 실제 사용 조언
고정 크기, 빠른 반복/접근이 필요하다면 배열이 유리합니다.
크기가 가변적이거나, 데이터 추가/삭제가 빈번하다면 벡터가 적합합니다.
대용량 데이터 처리에서 벡터는 힙 할당 및 재할당 비용이 있으므로, 성능이 민감한 경우 벡터의 용량을 미리 예약(with_capacity)하는 것이 좋습니다.
※with_capacity란?
Vec::with_capacity는 Rust의 벡터(Vec)를 생성할 때 초기 용량(capacity) 을 미리 지정하는 메서드입니다.
with_capacity(n)은 최소 n개의 요소를 저장할 수 있는 공간을 미리 할당한 빈 벡터를 생성합니다.
이렇게 하면, 벡터에 요소를 추가할 때마다 메모리를 재할당하는 비용을 줄일 수 있어 성능이 향상됩니다.
