pub struct RemovableHeap<T> { /* private fields */ }
Expand description

削除可能ヒープ。

Idea

ヒープを二つ使う。

Implementation notes

peek()&self にするため、remove()pop() の直後はとりあえず force() している。

Examples

use nekolib::ds::RemovableHeap;

let mut heap = RemovableHeap::new();
heap.push(2);
heap.push(1);
heap.push(3);
heap.push(0);
assert_eq!(heap.peek(), Some(&3)); // {0, 1, 2, 3}

heap.remove(2);                    // {0, 1, 3}
assert_eq!(heap.pop(), Some(3));   // {0, 1}
assert_eq!(heap.peek(), Some(&1));
heap.remove(1);                    // {0}
assert_eq!(heap.peek(), Some(&0));
assert_eq!(heap.pop(), Some(0));   // {}
assert!(heap.is_empty());

削除する要素がヒープに入っていないとき、こまる。

use nekolib::ds::RemovableHeap;

let mut heap = RemovableHeap::new();
heap.push(1);
heap.remove(2);
heap.push(2);
heap.push(3);                      // {1, 2, 3}?
assert_eq!(heap.pop(), Some(3));   // seems good?
assert_ne!(heap.peek(), Some(&2)); // but...
assert_eq!(heap.peek(), Some(&1));

未来の push 操作を打ち消すというわけでもない。

use nekolib::ds::RemovableHeap;

let mut heap = RemovableHeap::new();
heap.push(1);
heap.push(2);
heap.remove(100);
heap.remove(3);
heap.push(101);
heap.push(3);                      // {1, 2, 101}?
assert_eq!(heap.pop(), Some(101)); // seems good, so far
assert_ne!(heap.peek(), Some(&2)); // but...
assert_eq!(heap.peek(), Some(&3));

Implementations§

source§

impl<T: Ord> RemovableHeap<T>

source

pub fn new() -> Self

空のヒープで初期化する。

source

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

要素を追加する。

source

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

要素を削除する。

Notes

削除処理を遅延させて行うため、&T ではなく T であることに注意。

また、item はその時点でヒープに入っている要素のいずれかと等しい必要がある。 「未来に追加される要素を打ち消す」あるいは「単に無視する」という仕様は、 どちらも操作順しだいでどちらもうまくいかなくなるはず。

BTreeSet を使えば判定できるが、それなら最初から BTreeSet でやればよい。

source

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

最大値を取り出す。

source

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

最大値を取得する。

source

pub fn is_empty(&self) -> bool

空のとき true を返す。

source

pub fn len(&self) -> usize

要素数を返す。

Trait Implementations§

source§

impl<T: Clone> Clone for RemovableHeap<T>

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more

Auto Trait Implementations§

§

impl<T> RefUnwindSafe for RemovableHeap<T>where T: RefUnwindSafe,

§

impl<T> Send for RemovableHeap<T>where T: Send,

§

impl<T> Sync for RemovableHeap<T>where T: Sync,

§

impl<T> Unpin for RemovableHeap<T>where T: Unpin,

§

impl<T> UnwindSafe for RemovableHeap<T>where T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V