it seem that I found some error in heap

[nesteiner]

I remember that rust's index is from 0, and your code is

pub fn add(&mut self, value: T) {
        self.count += 1;
        self.items.push(value);

        // Heapify Up
        let mut idx = self.count;
        while self.parent_idx(idx) > 0 {
            let pdx = self.parent_idx(idx);
            if (self.comparator)(&self.items[idx], &self.items[pdx]) {
                self.items.swap(idx, pdx);
            }
            idx = pdx;
        }
    }

the idx should be self.count - 1
and the parent_index, left_child_index, right_index are wrong too,
the parent_index should be (index - 1) / 2, left_child should be 2 * index + 1, right_child should be 2 * index + 2

[nesteiner]

and this code

fn children_present(&self, idx: usize) -> bool {
        self.left_child_idx(idx) <= self.count
    }

should be

self.left_child_idx(idx) == self.count - 1

[nesteiner]

maybe you can try this code

use std::cmp::Ord;
use std::slice::Iter;
use std::fmt::{self, Display, Formatter};

impl <T> Heap<T> {
    pub fn new(comparator: fn(&T, &T) -> bool) -> Self {
	Self {
	    count: 0,
	    items: Vec::new(),
	    comparator,
	}
    }

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

    pub fn push(&mut self, value: T) {
	let mut ipos = self.items.len();
	let mut ppos = self.parent_index(ipos);
	self.items.push(value);

	while ipos > 0 && (self.comparator)(&self.items[ipos], &self.items[ppos]) {
	    self.items.swap(ipos, ppos);

	    ipos = ppos;
	    ppos = self.parent_index(ipos);
	}

	self.count += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
	if self.count == 0 {
	    return None;
	}

	self.items.swap(0, self.count - 1);
	self.count -= 1;

	let mut ipos = 0;
	let mut mpos = 0;

	loop {
	    let lpos = self.left_child(ipos);
	    let rpos = self.right_child(ipos);

	    if lpos < self.count && (self.comparator)(&self.items[lpos], &self.items[ipos]) {
		mpos = lpos;
	    } else {
		mpos = ipos;
	    }

	    if rpos < self.count && (self.comparator)(&self.items[rpos], &self.items[mpos]) {
		mpos = rpos;
	    }

	    if mpos == ipos {
		break;
	    } else {
		self.items.swap(mpos, ipos);
		ipos = mpos
	    }
	}

	return Some(self.items.remove(0));
    }


    pub fn iter(&self) -> HeapIter<'_, T> {
	return HeapIter {
	    node: self.items.iter()
	}
    }

    pub fn is_empty(&self) -> bool {
	return self.count == 0;
    }

    fn parent_index(&self, index: usize) -> usize {
	index.wrapping_sub(1) / 2
    }

    fn children_present(&self, index: usize) -> bool {
	self.left_child(index) == self.count - 1
    }

    fn left_child(&self, index: usize) -> usize {
	index * 2 + 1
    }

    fn right_child(&self, index: usize) -> usize {
	index * 2 + 2
    }
}

impl <T> Heap<T> where T: Ord {
    pub fn new_min() -> Heap<T> {
	Self::new(|a, b| a < b)
    }

    pub fn new_max() -> Heap<T> {
	Self::new(|a, b| a > b)
    }
}

impl <'a, T> Iterator for HeapIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
	return self.node.next();
    }
}

impl <T> Display for Heap<T> where T: Display {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
	for value in self.iter() {
	    write!(f, "{}", value)?
	}

	write!(f, "")
    }
}

[siriak]

Could you add a test that shows that there's a bug?

[siriak]

Please make a PR with the test and a fix for the issue, thanks!

[nesteiner]

oh, I don't know how, you can forget it 🙂

[guuzaa]

Actually, both ways are correct. They are just two different ways to store the first item of the heap. As a result, parent_index, left_child_index, right_child_index are different.

impl <T> Heap<T> {
    pub fn new(comparator: fn(&T, &T) -> bool) -> Self {
	Self {
	    count: 0,
	    items: Vec::new(),
	    comparator,
	}
    }

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

    pub fn push(&mut self, value: T) {
	let mut ipos = self.items.len();
	let mut ppos = self.parent_index(ipos);
	self.items.push(value);

	while ipos > 0 && (self.comparator)(&self.items[ipos], &self.items[ppos]) {
	    self.items.swap(ipos, ppos);

	    ipos = ppos;
	    ppos = self.parent_index(ipos);
	}

	self.count += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
	if self.count == 0 {
	    return None;
	}

	self.items.swap(0, self.count - 1);
	self.count -= 1;

	let mut ipos = 0;
	let mut mpos = 0;

	loop {
	    let lpos = self.left_child(ipos);
	    let rpos = self.right_child(ipos);

	    if lpos < self.count && (self.comparator)(&self.items[lpos], &self.items[ipos]) {
		mpos = lpos;
	    } else {
		mpos = ipos;
	    }

	    if rpos < self.count && (self.comparator)(&self.items[rpos], &self.items[mpos]) {
		mpos = rpos;
	    }

	    if mpos == ipos {
		break;
	    } else {
		self.items.swap(mpos, ipos);
		ipos = mpos
	    }
	}

	return Some(self.items.remove(0));
    }


    pub fn iter(&self) -> HeapIter<'_, T> {
	return HeapIter {
	    node: self.items.iter()
	}
    }

    pub fn is_empty(&self) -> bool {
	return self.count == 0;
    }

    fn parent_index(&self, index: usize) -> usize {
	index.wrapping_sub(1) / 2
    }

    fn children_present(&self, index: usize) -> bool {
	self.left_child(index) == self.count - 1
    }

    fn left_child(&self, index: usize) -> usize {
	index * 2 + 1
    }

    fn right_child(&self, index: usize) -> usize {
	index * 2 + 2
    }
}

In the above code, you store the first item of the heap at index 0.
In this repo, they store it at index 1.
If you store it at index 0, index has to substract 1, which could lead to overflow.
So I recommend you store the first item at index 1, as this repo does.