Comments (6)
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.
from rust.
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
from rust.
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, "")
}
}
from rust.
Could you add a test that shows that there's a bug?
from rust.
Please make a PR with the test and a fix for the issue, thanks!
from rust.
oh, I don't know how, you can forget it 🙂
from rust.
Related Issues (20)
- ...and how do you use them? HOT 1
- Linked List implementation is unsound HOT 3
- github actions is in outdated version HOT 2
- Authentication is needed to run workflows for PR HOT 7
- Suggestion: Add a Section for Bit Manipulation Algorithms HOT 3
- Suggestion: Adding Loss functions of Machine Learning in maths folder HOT 19
- Suggestion: Add optimization functions, ml algorithms under `machine_learning` folder HOT 10
- Suggestion: Parallel Implementation HOT 3
- DIRECTORY.md is out of date HOT 9
- Many implementations are not declared as mods anywhere in the module tree HOT 1
- Add Gitpod Setup
- Add algorithm to find k-th digit in a digit string HOT 2
- Add algorithm to find a number of points in a polygon area
- Suggestion: Adding Geometry, Graph and Number Theory as subfolders of Math HOT 6
- Suggestion: Add diff and zero-crossing rate algoritms for math HOT 2
- Fails miri test for rb-tree on Rust HOT 2
- String based algorithms panics on unicode characters HOT 3
- Automating mod files HOT 2
- A small bug in Quick Select algorithm HOT 1
- God repository
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rust.