add generic heap implementation #4
Conversation
fix file structure
| #[derive(Debug, Default, Clone, PartialOrd, PartialEq)] | ||
| pub struct Node<K, V> { | ||
| pub key: K, | ||
| pub value: V, |
There was a problem hiding this comment.
Fixed node struct to include V for arbitrary metadata
| } | ||
| } | ||
|
|
||
| fn _heapifydown(&mut self, index: usize) { |
There was a problem hiding this comment.
iterative implementation of all previously recursive functions ✅
| } | ||
|
|
||
| #[derive(Debug)] | ||
| pub struct BinaryHeapIterator< |
|
Please remove the .DS_Store file from the PR |
|
Why are there so many changes in the other files? |
| } | ||
| }) | ||
| } | ||
|
|
There was a problem hiding this comment.
Can you paste the benchmark stats?
There was a problem hiding this comment.
test bench_tests::bench_sokoban_binary_heap_insert_1000_u128 ... bench: 44,853 ns/iter (+/- 617)
test bench_tests::bench_sokoban_binary_heap_insert_20000_u128 ... bench: 45,293 ns/iter (+/- 1,492)
test bench_tests::bench_sokoban_binary_heap_remove_1000_u128 ... bench: 91,893 ns/iter (+/- 415)
test bench_tests::bench_std_binary_heap_insert_1000_u128 ... bench: 42,571 ns/iter (+/- 1,718)
test bench_tests::bench_std_binary_heap_insert_20000_u128 ... bench: 846,477 ns/iter (+/- 43,306)
test bench_tests::bench_std_binary_heap_remove_1000_u128 ... bench: 70,234 ns/iter (+/- 3,002)
src/binary_heap.rs
Outdated
| self.size += 1; | ||
| } | ||
|
|
||
| pub fn _pop_min(&mut self) { |
There was a problem hiding this comment.
I don't think this index is guaranteed to be the "min"
PR to add a generic heap data structure that fits into fixed buffers.
Tried to make the tests comparable to data structures implemented with
NodeAllocator.