Binary Heap Implementation

A binary heap is a complete binary tree stored compactly inside a flat Vec<T> without node pointers, satisfying the heap property where every parent compares greater than or equal to (max-heap) or less than or equal to (min-heap) its children. Supporting indexed key updates (decrease_key / update_priority) via an auxiliary handle map makes the heap directly usable in graph shortest-path and task-scheduling algorithms.

Array-Backed Complete Binary Tree Layout

Index mapping for 0-based array:
  parent(i)      = (i - 1) / 2
  left_child(i)  = 2 * i + 1
  right_child(i) = 2 * i + 2

        [0: prio=2]
        /         \
  [1: prio=5]   [2: prio=4]
    /     \       /
[3: 9]  [4: 7] [5: 8]

Flat Vec storage: [ (2), (5), (4), (9), (7), (8) ]

Complete Indexed Min-Heap Implementation

use std::collections::HashMap;
use std::hash::Hash;

#[derive(Debug, Clone)]
struct HeapNode<K, P> {
    key: K,
    priority: P,
}

pub struct IndexedMinHeap<K, P> {
    nodes: Vec<HeapNode<K, P>>,
    positions: HashMap<K, usize>,
}

impl<K: Hash + Eq + Clone, P: Ord + Clone> IndexedMinHeap<K, P> {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            positions: HashMap::new(),
        }
    }

    pub fn from_entries(entries: Vec<(K, P)>) -> Self {
        let mut nodes = Vec::with_capacity(entries.len());
        let mut positions = HashMap::with_capacity(entries.len());
        for (idx, (key, priority)) in entries.into_iter().enumerate() {
            positions.insert(key.clone(), idx);
            nodes.push(HeapNode { key, priority });
        }
        let mut heap = Self { nodes, positions };
        // Floyd's linear-time O(n) heap construction
        if heap.nodes.len() > 1 {
            for i in (0..=(heap.nodes.len() / 2 - 1)).rev() {
                heap.sift_down(i);
            }
        }
        heap
    }

    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    pub fn peek(&self) -> Option<(&K, &P)> {
        self.nodes.first().map(|n| (&n.key, &n.priority))
    }

    pub fn priority_of(&self, key: &K) -> Option<&P> {
        let &idx = self.positions.get(key)?;
        Some(&self.nodes[idx].priority)
    }

    pub fn push_or_update(&mut self, key: K, priority: P) -> bool {
        if let Some(&idx) = self.positions.get(&key) {
            self.nodes[idx].priority = priority;
            self.sift_up(idx);
            self.sift_down(idx);
            false
        } else {
            let idx = self.nodes.len();
            self.positions.insert(key.clone(), idx);
            self.nodes.push(HeapNode { key, priority });
            self.sift_up(idx);
            true
        }
    }

    pub fn pop(&mut self) -> Option<(K, P)> {
        if self.nodes.is_empty() {
            return None;
        }
        let last_idx = self.nodes.len() - 1;
        self.swap_nodes(0, last_idx);
        let removed = self.nodes.pop().unwrap();
        self.positions.remove(&removed.key);

        if !self.nodes.is_empty() {
            self.sift_down(0);
        }
        Some((removed.key, removed.priority))
    }

    fn swap_nodes(&mut self, a: usize, b: usize) {
        if a == b {
            return;
        }
        self.nodes.swap(a, b);
        let key_a = self.nodes[a].key.clone();
        let key_b = self.nodes[b].key.clone();
        self.positions.insert(key_a, a);
        self.positions.insert(key_b, b);
    }

    fn sift_up(&mut self, mut idx: usize) {
        while idx > 0 {
            let parent = (idx - 1) / 2;
            if self.nodes[idx].priority < self.nodes[parent].priority {
                self.swap_nodes(idx, parent);
                idx = parent;
            } else {
                break;
            }
        }
    }

    fn sift_down(&mut self, mut idx: usize) {
        let len = self.nodes.len();
        loop {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let mut smallest = idx;

            if left < len && self.nodes[left].priority < self.nodes[smallest].priority {
                smallest = left;
            }
            if right < len && self.nodes[right].priority < self.nodes[smallest].priority {
                smallest = right;
            }
            if smallest != idx {
                self.swap_nodes(idx, smallest);
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

fn main() {
    let initial = vec![
        ("worker-a", 45),
        ("worker-b", 12),
        ("worker-c", 80),
        ("worker-d", 25),
        ("worker-e", 5),
    ];

    let mut heap = IndexedMinHeap::from_entries(initial);
    println!("After O(n) Floyd build-heap, peek = {:?}", heap.peek());

    // Dynamically lower the priority cost of 'worker-c' from 80 to 2
    heap.push_or_update("worker-c", 2);
    println!(
        "After updating 'worker-c' priority to 2, peek = {:?}",
        heap.peek()
    );

    println!("\nDrain order:");
    while let Some((worker, cost)) = heap.pop() {
        println!("  {} -> cost {}", worker, cost);
    }
}

After O(n) Floyd build-heap, peek = Some((&"worker-e", &5))
After updating 'worker-c' priority to 2, peek = Some((&"worker-c", &2))

Drain order:
  worker-c -> cost 2
  worker-e -> cost 5
  worker-b -> cost 12
  worker-d -> cost 25
  worker-a -> cost 45