Struct rudac::heap::MinMax

pub struct MinMax<T: Ord> { /* fields omitted */ }

A min-max heap provides constant time retrieval and logarithmic time removal of both the min and max elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue

Examples

use rudac::heap::MinMax;

// you can either initialize an empty heap with zero initial capacity
let empty_heap: MinMax<usize> = MinMax::init();

// or an empty heap with initial capacity to reduce relocation
let with_cap_heap: MinMax<usize> = MinMax::with_capacity(128);

// or construct a min-max heap from an existing vector
let built_heap = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

// inspect max or min values
assert_eq!(*built_heap.peek_min().unwrap(), 1);
assert_eq!(*built_heap.peek_max().unwrap(), 11);

Implementations

impl<T: Ord> MinMax<T>

pub fn init() -> MinMax<T>

Initializes a heap with zero capacity

Examples

use rudac::heap::MinMax;

let minmax: MinMax<usize> = MinMax::init();

assert_eq!(minmax.capacity(), 0);

pub fn with_capacity(capacity: usize) -> MinMax<T>

Initializes a heap with specified capacity

Examples

use rudac::heap::MinMax;

let minmax: MinMax<usize> = MinMax::with_capacity(128);

assert_eq!(minmax.capacity(), 128);

pub fn build_heap(vector: Vec<T>) -> MinMax<T>

Builds a heap using a bottom-up approach.

• Complexity: O(n)

Arguments

• vector: vector to build the heap from

Examples

use rudac::heap::MinMax;

let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(*minmax.peek_min().unwrap(), 1);
assert_eq!(*minmax.peek_max().unwrap(), 11);

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

Pushes an item into the heap

• Complexity: O(log n)

Arguments

• item: data to be pushed into the heap

Examples

use rudac::heap::MinMax;

let mut minmax: MinMax<usize> = MinMax::init();

minmax.push(10);
minmax.push(5);
minmax.push(1);
minmax.push(4);
minmax.push(3);
minmax.push(12);

assert_eq!(*minmax.peek_min().unwrap(), 1);
assert_eq!(*minmax.peek_max().unwrap(), 12);

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

Returns a reference to the min value. returns None if heap is empty

• Complexity: O(1)

Examples

use rudac::heap::MinMax;

let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(*minmax.peek_min().unwrap(), 1);

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

Returns a reference to the max value. returns None if heap is empty

• Complexity: O(1)

Examples

use rudac::heap::MinMax;

let minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(*minmax.peek_max().unwrap(), 11);

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

Pops min value from heap and returns it. returns None if heap is empty

• Complexity: O(log n)

Examples

use rudac::heap::MinMax;

let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(minmax.pop_min().unwrap(), 1);
assert_eq!(*minmax.peek_min().unwrap(), 2);

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

Pops max value from heap and returns it. returns None if heap is empty

• Complexity: O(log n)

Examples

use rudac::heap::MinMax;

let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(minmax.pop_max().unwrap(), 11);
assert_eq!(*minmax.peek_max().unwrap(), 9);

pub fn push_pop_min(&mut self, item: T) -> Option<T>

Pops and returns the min value and pushes the item into heap without allocating.

• Complexity: O(log n)

Arguments

• item: data to be pushed into the heap

Examples

use rudac::heap::MinMax;

let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 0]);

assert_eq!(minmax.push_pop_min(13).unwrap(), 0);
assert_eq!(*minmax.peek_min().unwrap(), 2);
assert_eq!(*minmax.peek_max().unwrap(), 13);

pub fn push_pop_max(&mut self, item: T) -> Option<T>

Pops and returns the max value and pushes the item into heap without allocating.

• Complexity: O(log n)

Arguments

• item: data to be pushed into the heap

Examples

use rudac::heap::MinMax;

let mut minmax = MinMax::build_heap(vec![9, 8, 2, 3, 4, 5, 11, 6, 7, 1]);

assert_eq!(minmax.push_pop_max(0).unwrap(), 11);
assert_eq!(*minmax.peek_min().unwrap(), 0);
assert_eq!(*minmax.peek_max().unwrap(), 9);

pub fn replace_min(&mut self, item: T) -> Option<T>

Pops and returns the min value and pushes the item into heap without allocating.

• Complexity: O(log n)

Arguments

• item: data to be pushed into the heap

Examples

use rudac::heap::MinMax;

let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);
     
assert_eq!(minmax.replace_min(4).unwrap(), 1);
assert_eq!(*minmax.peek_min().unwrap(), 2);
assert_eq!(*minmax.peek_max().unwrap(), 4);

pub fn replace_max(&mut self, item: T) -> Option<T>

Pops and returns the max value and pushes the item into heap without allocating.

• Complexity: O(log n)

Arguments

• item: data to be pushed into the heap

Examples

use rudac::heap::MinMax;

let mut minmax: MinMax<usize> = MinMax::build_heap(vec![3, 2, 1]);

assert_eq!(minmax.replace_max(4).unwrap(), 3);
assert_eq!(*minmax.peek_min().unwrap(), 1);
assert_eq!(*minmax.peek_max().unwrap(), 4);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for additional more items to be pushed into heap

pub fn reserve_exact(&mut self, additional: usize)

Reserves capacity for additional more items to be pushed into heap

pub fn shrink_to_fit(&mut self)

Shrinks capacity internal vector to fit the existing data

pub fn into_vec(self) -> Vec<T>

Consumes the heap and returns the internal vector

pub fn size(&self) -> usize

Total number of elements in the heap

pub fn is_empty(&self) -> bool

Returns true if heap is empty, false otherwise

pub fn clear(&mut self)

Clears the internal vector

pub fn capacity(&self) -> usize

Returns capacity of the heap