Struct MinHeap 

pub struct MinHeap<T>(/* private fields */);

最小値を優先して取り出すヒープです。

push と pop は O(log N)、peek は O(1) です。

Examples

use atcoder::data_structure::heap::MinHeap;

let mut heap = MinHeap::new();
heap.push(3);
heap.push(1);
assert_eq!(heap.pop(), Some(1));

Implementations

impl<T: Ord> MinHeap<T>

pub fn new() -> Self

空の最小ヒープを作ります。計算量は O(1) です。

pub fn push(&mut self, item: T)

要素を追加します。計算量は O(log N) です。

pub fn pop(&mut self) -> Option<T>

最小要素を削除して返します。空なら None です。計算量は O(log N) です。

pub fn peek(&self) -> Option<&T>

最小要素への参照を返します。空なら None です。計算量は O(1) です。

pub fn len(&self) -> usize

要素数を返します。計算量は O(1) です。

pub fn is_empty(&self) -> bool

空なら true を返します。計算量は O(1) です。

Trait Implementations

impl<T: Clone> Clone for MinHeap<T>

fn clone(&self) -> MinHeap<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for MinHeap<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Default for MinHeap<T>

fn default() -> Self

Returns the “default value” for a type.