Intrusive Heap

Showcase
1

Hello! I built a Heap :+1:

I needed a very high performance heap for a discrete event simulation, so I took the std.PriorityQueue implementation and added two things, inspiring with the Intrusive interface concept: if the element you enter in the heap contains its position on the heap I can access it in $O(1)$ time. Every time the element gets moved, I update the index on the element; this does not affect any struct other than the ones that contain a “heap_index” field, and it does not add overhead thanks to compile-time execution :D. If you wanna know why I needed that I can go into more detail haha

Additionaly, I generalized the structure to a $d$-ary heap to improve cache hits and make it more performant, tho I have not tested how much fast does it go (nor understand why cache hits improve with more children per node so xd)

Also, I rewrote the struct to be more new ArrayList like, so fully Unmanaged and not storing the allocator, which ends up also as a very nice api :slight_smile:

If you see some suboptimal code or suggestion please let me know!! Have a nice day :))

Edit: forgot the link

4 Likes
2

Small note on this that i forgot: normally a heap is $O(log N)$ to remove the first element, and to remove an arbitrary element is $O(N)$ as the Priority Queue is not sorted.
The intrusive index allows the Heap to have the same cost of removal for every element from the heap, due to the look up being instant :slight_smile:

In my case, an event of the simulation might involve deleting some scheduled events from the future, which makes it exactly what I need!