Struct Heap

pub struct Heap<T> {
    pub values: Vec<T>,
    pub is_max_heap: bool,
}

A binary heap data structure that can be either a max-heap or a min-heap.

A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, for every node i other than the root, the value of i is less than or equal to the value of its parent. Similarly, in a min-heap, for every node i other than the root, the value of i is greater than or equal to the value of its parent.

This implementation allows you to specify whether the heap is a max-heap or a min-heap when creating it.

Fields

values: Vec<T>

The values stored in the heap.

This vector maintains the heap property, where the values are ordered according to whether the heap is a max-heap or a min-heap.

is_max_heap: bool

Whether the heap is a max-heap or a min-heap.

If true, the heap will be a max-heap; if false, the heap will be a min-heap.

Implementations

impl<T: Ord> Heap<T>

pub fn new(is_max_heap: bool) -> Self

Creates a new empty heap.

Parameters

• is_max_heap: A boolean flag indicating whether the heap is a max-heap (true) or a min-heap (false).

Returns

A new Heap instance with no elements.

Example

use dsa::data_structures::heap::Heap;
 
let heap: Heap<i32> = Heap::new(true);
assert_eq!(heap.is_max_heap, true);

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

Inserts a new value into the heap

Parameters

• value: The value to insert into the heap

Examples

use dsa::data_structures::heap::Heap;
 
let mut heap = Heap::new(true);

heap.insert(3);
heap.insert(1);
heap.insert(2);
heap.build_heap();
 
assert_eq!(heap.values, vec![3, 1, 2]);

pub fn build_heap(&mut self)

Builds the heap from the current values.

This method ensures that the values stored in the heap follow the heap property. It works by repeatedly calling the sift_down function on each non-leaf node, starting from the last non-leaf node and going up to the root.

Example

use dsa::data_structures::heap::Heap;
 
let mut heap = Heap::new(true);

heap.insert(3);
heap.insert(1);
heap.insert(2);
heap.build_heap();

assert_eq!(heap.values, vec![3, 1, 2]);

pub fn sift_down(&mut self, index: usize, len: usize)

Sifts down a value in the heap to maintain the heap property.

This function compares the current node with its children and swaps it with the larger (or smaller) child, depending on whether it’s a max-heap or min-heap. The process is repeated recursively until the heap property is restored.

Parameters

• index: The index of the current node that needs to be sifted down.
• len: The total length of the heap (used to avoid out-of-bounds errors).