Skip to main content

PriorityQueue

d_ary_heap

Struct PriorityQueue 

Source 
pub struct PriorityQueue<T, C>
where
    T: Eq + Hash + Clone,
{ /* private fields */ }
Expand description

d-ary heap priority queue with O(1) item lookup.

Type Parameters:

  • T: Item type (must implement Eq + Hash + Clone)
  • C: Comparator implementing PriorityCompare<T>

Cross-language equivalents:

  • C++: TOOLS::PriorityQueue<T, THash, TComparisonPredicate, TEqual>
  • Zig: DHeap(T, HashContext(T), Comparator(T))
  • TypeScript: PriorityQueue<T, K>

§Examples

use d_ary_heap::{PriorityQueue, MinBy};

// Create min-heap with arity 3
let mut heap = PriorityQueue::new(3, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);
heap.insert(7);

assert_eq!(heap.front(), &3);
assert_eq!(heap.len(), 3);

Time Complexities (n = number of items, d = arity):

  • new(): O(1)
  • insert(): O(log_d n)
  • front()/peek(): O(1)
  • pop(): O(d · log_d n)
  • increase_priority(): O(log_d n)
  • decrease_priority(): O(d · log_d n)
  • contains(): O(1)
  • len()/is_empty()/d(): O(1)

Implementations§

Source§

impl<T, C> PriorityQueue<T, C>
where T: Eq + Hash + Clone, C: PriorityCompare<T>,

Source

pub fn new(d: usize, comparator: C) -> Result<Self, Error>

Creates a new empty d-ary heap with specified arity and comparator.

§Arguments
  • d - Arity (number of children per node). Must be ≥ 1.
  • comparator - Defines priority order (min-heap or max-heap)
§Errors

Returns Error::InvalidArity if d == 0.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, MaxBy, Error};

// Binary heap (d=2) with min-heap ordering
let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();

// Quaternary heap (d=4) with max-heap ordering
let mut heap = PriorityQueue::new(4, MaxBy(|x: &i32| *x)).unwrap();

// Invalid arity returns error
assert!(PriorityQueue::new(0, MinBy(|x: &i32| *x)).is_err());

Cross-language equivalents:

  • C++: PriorityQueue<T>(d)
  • Zig: DHeap.init(d, comparator, allocator) (returns !T)
  • TypeScript: new PriorityQueue({d, comparator, keyExtractor}) (throws)
  • Go: New(d, comparator) (returns *T, error)
Source

pub fn with_first(d: usize, comparator: C, t: T) -> Result<Self, Error>

Creates a new d-ary heap with specified arity, inserting the first item.

§Arguments
  • d - Arity (number of children per node). Must be ≥ 1.
  • comparator - Defines priority order
  • t - First item to insert
§Errors

Returns Error::InvalidArity if d == 0.

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::with_first(3, MinBy(|x: &i32| *x), 42).unwrap();
assert_eq!(heap.front(), &42);

Cross-language equivalents:

  • C++: PriorityQueue(d, t)
  • Zig: Not directly available (use init + insert)
  • TypeScript: PriorityQueue.withFirst(options, item)
  • Go: WithFirst(d, comparator, item) (returns *T, error)
Source

pub fn d(&self) -> usize

Returns the arity (number of children per node) of this heap.

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let heap = PriorityQueue::new(4, MinBy(|x: &i32| *x)).unwrap();
assert_eq!(heap.d(), 4);

Cross-language equivalents:

  • C++: d()
  • Zig: d()
  • TypeScript: d()
Source

pub fn len(&self) -> usize

Returns the number of items in the heap.

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
assert_eq!(heap.len(), 0);
heap.insert(5);
assert_eq!(heap.len(), 1);

Cross-language equivalents:

  • C++: len()
  • Zig: len()
  • TypeScript: len()
Source

pub fn is_empty(&self) -> bool

Returns true if the heap is empty.

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
assert!(heap.is_empty());
heap.insert(5);
assert!(!heap.is_empty());

Cross-language equivalents:

  • C++: is_empty()
  • Zig: isEmpty()
  • TypeScript: isEmpty()
Source

pub fn contains(&self, item: &T) -> bool

Checks if an item exists in the heap by identity (O(1) lookup).

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
assert!(heap.contains(&5));
assert!(!heap.contains(&10));

Cross-language equivalents:

  • C++: contains(item)
  • Zig: contains(item)
  • TypeScript: contains(item)
Source

pub fn get_position(&self, item: &T) -> Option<Position>

Returns the position (index) of an item in the heap, or None if not found.

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);

// Root item (highest priority) is at position 0
assert_eq!(heap.get_position(&3), Some(0));
assert!(heap.get_position(&5).is_some());
assert_eq!(heap.get_position(&99), None);

Cross-language equivalents:

  • C++: get_position(item)
  • Zig: getPosition(item)
  • TypeScript: getPosition(item)
  • Go: GetPosition(item)
Source

pub fn clear(&mut self, d: Option<usize>) -> Result<(), Error>

Clears all items from the heap, optionally changing the arity.

Time Complexity: O(1)

§Errors

Returns Error::InvalidArity if d is Some(0).

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);

heap.clear(None).unwrap();
assert!(heap.is_empty());
assert_eq!(heap.d(), 2); // Arity preserved

heap.clear(Some(4)).unwrap(); // Change arity to 4
assert_eq!(heap.d(), 4);

// Invalid arity returns error
assert!(heap.clear(Some(0)).is_err());

Cross-language equivalents:

  • C++: clear(opt_d)
  • Zig: clear(new_depth?) (returns !void)
  • TypeScript: clear(newD?) (throws on invalid)
  • Go: Clear(d) (returns error)
Source

pub fn front(&self) -> &T

Returns a reference to the highest-priority item.

Time Complexity: O(1)

§Panics

Panics if the heap is empty.

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);

assert_eq!(heap.front(), &3);

Cross-language equivalents:

  • C++: front() (UB if empty)
  • Zig: front() (returns null if empty)
  • TypeScript: front() (throws if empty)

Safe alternative: Use peek() instead.

Source

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

Safe alternative to front() that returns None if empty.

Time Complexity: O(1)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
assert_eq!(heap.peek(), None);

heap.insert(5);
assert_eq!(heap.peek(), Some(&5));

Cross-language equivalents:

  • C++: peek()
  • Zig: front() / peek()
  • TypeScript: peek()
  • Go: Peek()
Source

pub fn insert(&mut self, t: T)

Inserts an item into the heap according to its priority.

Time Complexity: O(log_d n)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);
heap.insert(7);

assert_eq!(heap.front(), &3);

Cross-language equivalents:

  • C++: insert(item)
  • Zig: insert(item)
  • TypeScript: insert(item)
Source

pub fn increase_priority_by_index(&mut self, i: usize) -> Result<(), Error>

Increases priority of item at specified index (moves up if needed).

Time Complexity: O(log_d n)

§Errors

Returns Error::IndexOutOfBounds if index is out of bounds.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(10);
heap.insert(5);

// Increase priority of item at index 1
heap.increase_priority_by_index(1).unwrap();

// Error on out of bounds
assert_eq!(heap.increase_priority_by_index(99), Err(Error::IndexOutOfBounds));

Cross-language equivalents:

  • C++: increase_priority(position)
  • Zig: increasePriorityByIndex(index) (returns !void)
  • TypeScript: increasePriorityByIndex(index) (throws)
  • Go: IncreasePriorityByIndex(index) (returns error)
Source

pub fn decrease_priority_by_index(&mut self, i: usize) -> Result<(), Error>

Decreases priority of item at specified index (moves down if needed).

Time Complexity: O(d · log_d n)

§Errors

Returns Error::IndexOutOfBounds if index is out of bounds.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(10);
heap.insert(5);

// Decrease priority of item at index 0 (root)
heap.decrease_priority_by_index(0).unwrap();

// Error on out of bounds
assert_eq!(heap.decrease_priority_by_index(99), Err(Error::IndexOutOfBounds));

Cross-language equivalents:

  • C++: decrease_priority_by_index(index)
  • Zig: decreasePriorityByIndex(index) (returns !void)
  • TypeScript: decreasePriorityByIndex(index) (throws)
  • Go: DecreasePriorityByIndex(index) (returns error)
Source

pub fn update_priority_by_index(&mut self, i: usize) -> Result<(), Error>

Updates priority of item at specified index (moves in correct direction).

Use this when you don’t know whether the item’s priority increased or decreased. It will check both directions to maintain heap property.

Time Complexity: O((d+1) · log_d n) worst case

§Errors

Returns Error::IndexOutOfBounds if index is out of bounds.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(10);
heap.insert(5);

// Update priority at index - direction is determined automatically
heap.update_priority_by_index(0).unwrap();

// Error on out of bounds
assert_eq!(heap.update_priority_by_index(99), Err(Error::IndexOutOfBounds));

Cross-language equivalents:

  • C++: update_priority_by_index(index)
  • Zig: Not available
  • TypeScript: Not available
  • Go: Not available
Source

pub fn increase_priority(&mut self, updated_item: &T) -> Result<(), Error>

Increases priority of existing item (moves toward root if needed).

Time Complexity: O(log_d n)

§Errors

Returns Error::ItemNotFound if item is not in the heap.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(10);
heap.insert(5);

// The heap maintains proper ordering
assert_eq!(heap.front(), &5);
assert!(heap.contains(&10));

// Error on non-existent item
assert_eq!(heap.increase_priority(&99), Err(Error::ItemNotFound));

Note: For min-heap, “increase priority” means decreasing the priority value. For max-heap, “increase priority” means increasing the priority value.

Cross-language equivalents:

  • C++: increase_priority(item)
  • Zig: increasePriority(item) (returns !void)
  • TypeScript: increasePriority(item) (throws)
  • Go: IncreasePriority(item) (returns error)
Source

pub fn decrease_priority(&mut self, updated_item: &T) -> Result<(), Error>

Decreases priority of existing item (moves toward leaves if needed).

Important: Only call this when you know the item’s priority has decreased (become less important). For min-heap, this means the value increased. For max-heap, this means the value decreased. If unsure of the direction, use update_priority() instead.

Time Complexity: O(d · log_d n)

§Errors

Returns Error::ItemNotFound if item is not in the heap.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(10);

// The heap maintains proper ordering
assert_eq!(heap.front(), &5);
assert!(heap.contains(&10));

// Error on non-existent item
assert_eq!(heap.decrease_priority(&99), Err(Error::ItemNotFound));

Note: For min-heap, “decrease priority” means increasing the priority value. For max-heap, “decrease priority” means decreasing the priority value.

Cross-language equivalents:

  • C++: decrease_priority(item)
  • Zig: decreasePriority(item) (returns !void)
  • TypeScript: decreasePriority(item) (throws)
  • Go: DecreasePriority(item) (returns error)
Source

pub fn update_priority(&mut self, updated_item: &T) -> Result<(), Error>

Updates priority of existing item, moving it in the correct direction.

Use this when you don’t know whether the item’s priority increased or decreased. It will check both directions to maintain heap property.

Time Complexity: O((d+1) · log_d n) worst case

§Errors

Returns Error::ItemNotFound if item is not in the heap.

§Examples
use d_ary_heap::{PriorityQueue, MinBy, Error};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(10);

// Update priority - direction is determined automatically
heap.update_priority(&3).unwrap_or(()); // Would need matching item by identity

// Error on non-existent item
assert_eq!(heap.update_priority(&99), Err(Error::ItemNotFound));

Cross-language equivalents:

  • C++: update_priority(item) / try_update_priority(item)
  • Zig: updatePriority(item) (returns !void)
  • TypeScript: updatePriority(item) (throws)
  • Go: UpdatePriority(item) (returns error)
Source

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

Removes and returns the highest-priority item from the heap.

Returns None if the heap is empty.

Time Complexity: O(d · log_d n)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);
heap.insert(7);

assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(7));
assert_eq!(heap.pop(), None);

Cross-language equivalents:

  • C++: pop()
  • Zig: pop() (returns ?T)
  • TypeScript: pop() (returns T | undefined)
  • Go: Pop() (returns T, bool)
Source

pub fn to_array(&self) -> Vec<T>

Returns a copy of the heap contents as a Vec.

The root element (highest priority) is at index 0. The internal heap structure is preserved—this is NOT a sorted array.

Time Complexity: O(n)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);
heap.insert(7);

let arr = heap.to_array();
assert_eq!(arr.len(), 3);
assert_eq!(arr[0], 3); // Root is highest priority (min value)

Cross-language equivalents:

  • C++: to_array()
  • Zig: toArray()
  • TypeScript: toArray()
  • Go: ToArray()
Source

pub fn insert_many(&mut self, items: impl IntoIterator<Item = T>)

Inserts multiple items into the heap using Floyd’s heapify algorithm.

This is more efficient than inserting items one at a time when adding many items at once: O(n) vs O(n log n).

Time Complexity: O(n) where n is the number of items being inserted

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert_many(vec![5, 3, 7, 1, 9]);

assert_eq!(heap.len(), 5);
assert_eq!(heap.front(), &1);

Cross-language equivalents:

  • C++: insert_many(items)
  • Zig: insertMany(items)
  • TypeScript: insertMany(items)
  • Go: InsertMany(items)
Source

pub fn pop_many(&mut self, count: usize) -> Vec<T>

Removes and returns multiple highest-priority items from the heap.

Returns up to count items in priority order (highest priority first). If the heap has fewer items than requested, returns all available items.

Time Complexity: O(count · d · log_d n)

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert_many(vec![5, 3, 7, 1, 9]);

let items = heap.pop_many(3);
assert_eq!(items, vec![1, 3, 5]);
assert_eq!(heap.len(), 2);

// Requesting more than available returns all remaining
let remaining = heap.pop_many(10);
assert_eq!(remaining, vec![7, 9]);
assert!(heap.is_empty());

Cross-language equivalents:

  • C++: pop_many(count)
  • Zig: popMany(count)
  • TypeScript: popMany(count)
  • Go: PopMany(count)
Source§

impl<T, C> PriorityQueue<T, C>
where T: Eq + Hash + Clone + Display,

Additional methods available when T implements Display.

Source

pub fn to_string(&self) -> String

Produces a string representation of the heap contents.

Time Complexity: O(n)

This method provides explicit string conversion for API parity with C++, Zig, and TypeScript implementations.

§Examples
use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);

assert_eq!(heap.to_string(), "{3, 5}");

Cross-language equivalents:

  • C++: to_string()
  • Zig: toString() / to_string()
  • TypeScript: toString() / to_string()

Trait Implementations§

Source§

impl<T, C: Debug> Debug for PriorityQueue<T, C>
where T: Eq + Hash + Clone + Debug,

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T, C> Display for PriorityQueue<T, C>
where T: Eq + Hash + Clone + Display,

Display implementation for PriorityQueue.

Renders the queue contents in array layout: {item1, item2, ...}.

Cross-language equivalents:

  • C++: put(std::ostream&)
  • Zig: toString()
  • TypeScript: toString()

§Examples

use d_ary_heap::{PriorityQueue, MinBy};

let mut heap = PriorityQueue::new(2, MinBy(|x: &i32| *x)).unwrap();
heap.insert(5);
heap.insert(3);

// Uses Display trait
println!("{}", heap); // Output: {3, 5}
Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<T, C> Freeze for PriorityQueue<T, C>
where C: Freeze,

§

impl<T, C> RefUnwindSafe for PriorityQueue<T, C>
where C: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, C> Send for PriorityQueue<T, C>
where C: Send, T: Send,

§

impl<T, C> Sync for PriorityQueue<T, C>
where C: Sync, T: Sync,

§

impl<T, C> Unpin for PriorityQueue<T, C>
where C: Unpin, T: Unpin,

§

impl<T, C> UnwindSafe for PriorityQueue<T, C>
where C: UnwindSafe, T: UnwindSafe,

Blanket Implementations§

Source§

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

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

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

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where 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 T
where 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> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

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

Source§

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 T
where U: TryFrom<T>,

Source§

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.