`MaxPQ::insert` panics immediately when created via `default()` or `from_capacity()`

[Rohan-GRH]

Description:

Hi, I encountered a panic when invoking the MaxPQ::insert method on a MaxPQ instance created via MaxPQ::default(). The very first call to insert() panics because the underlying vector has length 0 but the code tries to insert at index 1. The related source code is shown below:

algorithmica/algorithmica/src/sort/heap_sort.rs

Lines 35 to 52 in 073d556

	/// This operation happens when given root `k` is become lesser than it,s
	/// children. Because we are maintaining the MaxHeap, so both child should
	/// be lesser than it's parent
	pub fn sink<T: Ord, F: Fn(&T, &T) -> bool>(arr: &mut [T], k: usize, n: usize, p: &F) {
	let mut k = k;
	while 2 * k < n {
	let mut j = 2 * k + 1;
	if j < n && p(&arr[j], &arr[j + 1]) {
	j += 1;
	}
	if !p(&arr[j], &arr[k]) {
	arr.swap(k, j);
	k = j;
	} else {
	break;
	}
	}
	}

The MaxPQ uses 1-based indexing (as seen in del_max accessing self.q[1], and swim checking k > 1). The vector q should have a dummy element at index 0. However, from_capacity only calls Vec::with_capacity(capacity + 1), which allocates capacity but does not insert any elements — the vector's length remains 0. When insert() is called:

1. self.n increments from 0 to 1
2. self.q.insert(1, value) tries to insert at index 1 in a vec of length 0
3. Vec::insert requires index <= len, so index 1 is invalid for length 0 → panic

Compare with from_arr, which calls q.resize_with(n + 1, Default::default) to properly populate the vector, so it works correctly.

The panic report is:

Panic: insertion index (is 1) should be <= len (is 0)
Location: algorithmica/src/pq/max_pq.rs:44:16

stack backtrace:
  0: __rustc::rust_begin_unwind
        at /rustc/1d23d06800271f651fad07bf22bf5e298138972e/library/std/src/panicking.rs:698:5
  1: core::panicking::panic_fmt
        at /rustc/1d23d06800271f651fad07bf22bf5e298138972e/library/core/src/panicking.rs:80:14
  2: alloc::vec::Vec<T,A>::insert_mut::assert_failed
  3: alloc::vec::Vec<T,A>::insert_mut
  4: alloc::vec::Vec<T,A>::insert
  5: algorithmica::pq::max_pq::MaxPQ::insert
        at algorithmica/src/pq/max_pq.rs:44:16

This crash is likely to be a bug of the library and can cause security issues.

How to reproduce it:

The PoC program is:

use algorithmica::pq::max_pq::MaxPQ;

fn main() {
    let mut pq = MaxPQ::default();
    pq.insert(42);
    // panics: "insertion index (is 1) should be <= len (is 0)"
}

The build command is like:

export RUSTFLAGS="-Zsanitizer=address -C opt-level=0 -C debuginfo=2"
export RUSTUP_TOOLCHAIN="nightly"

cargo +nightly afl build --target x86_64-unknown-linux-gnu

Environment:

• Discovered via fuzz testing
• OS / distro: Ubuntu 24.04