[Rust 공식문서 한국어 정리] 128. Rust BinaryHeap<T> 가이드

[Rust 공식문서 한국어 정리] 128. Rust BinaryHeap 가이드

원문 제목: Struct std::collections::BinaryHeap
작성자: The Rust Project

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📌 1. 서론 — 이 문서가 다루는 내용
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Rust의 BinaryHeap가 제공하는 이진 힙 기반 우선순위 큐를 상세히 다룹니다.
최대 힙의 동작 원리와 peek, pop, push 메서드의 시간 복잡도를 학습합니다.
BinaryHeap의 내부 구조와 Vec 기반 구현의 효율성을 정리합니다.
Ord 트레이트를 기반으로 한 우선순위 결정 방식을 설명합니다.
우선순위 큐, Top-K, 스케줄링 등의 대표적 사용 패턴을 다룹니다.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
🔑 2. 핵심 개념 4가지
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

① BinaryHeap — 이진 힙 기반 우선순위 큐(최대 힙)
② Ord — 요소의 우선순위 결정 기준
③ peek — O(1)로 최상위 요소 조회
④ push/pop — O(log n) 삽입과 추출

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📖 3. 주요 내용 상세
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

BinaryHeap은 이진 힙 기반의 우선순위 큐입니다.
기본적으로 최대 힙으로 동작하며 가장 큰 값이 루트에 위치합니다.
BinaryHeap::new()로 빈 힙을 생성합니다.
BinaryHeap::from(vec)으로 벡터로부터 힙을 구성합니다.
push(value)는 요소를 삽입하며 O(log n) 시간이 소요됩니다.
pop()은 최상위 요소를 제거하고 반환하며 O(log n) 시간이 소요됩니다.
peek()은 최상위 요소를 Option<&T>로 조회하며 O(1) 시간이 소요됩니다.
peek_mut()은 최상위 요소를 Option로 가변 참조합니다.
PeekMut가 drop되면 힙 속성이 자동으로 복원됩니다.
len()과 is_empty()로 크기를 확인합니다.
into_sorted_vec()은 힙을 정렬된 Vec으로 변환합니다.
이는 힙 정렬 알고리즘의 일환으로 O(n log n) 시간이 소요됩니다.
drain()은 모든 요소를 반복자로 제거합니다.
BinaryHeap은 Vec을 내부적으로 사용하여 메모리 효율적입니다.
Ord 트레이트의 역순으로 최소 힙을 구현할 수 있습니다.
Reverse를 사용하면 T의 역순으로 정렬되어 최소 힙처럼 동작합니다.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
🛠 4. 실전 활용
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Top-K 요소 추출에 BinaryHeap을 사용합니다.
작업 스케줄링에서 우선순위가 높은 작업부터 처리합니다.
Dijkstra 알고리즘에서 최단 거리 노드 선택에 우선순위 큐를 사용합니다.
Reverse로 감싸 최소 힙으로 동작하게 하여 최소값 우선 처리를 구현합니다.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ 5. 정리
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

BinaryHeap은 O(log n) 삽입/추출과 O(1) peek을 제공하는 우선순위 큐입니다.
최대 힙으로 동작하며 Reverse를 사용하면 최소 힙으로 전환됩니다.
Vec 기반 구현으로 메모리 효율적이며 알고리즘 구현에 필수적입니다.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
🔗 출처 링크
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

원문: https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
BinaryHeap Methods: https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html

#Rust #BinaryHeap #우선순위큐 #힙 #번역