BinaryHeap (優先度付きキュー)

Overview

優先度付きキューについて

Code

• max-heap

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(5);
heap.push(2);

assert_eq!(heap.peak(), Some(&5));

assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

• min-heap

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

let mut heap = BinaryHeap::new();

heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));

assert_eq!(heap.peak(), Some(&Reverse(1)));

assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
let el = heap.pop().unwrap();
assert_eq!(5, el.0);
assert_eq!(heap.pop(), Some(Reverse(5)));

Detail

rustcのバージョンが1.15.1の場合、std::cmp::Reverseが使えない。