Interval Heap vs MinHeap

Fragment of a discussion from User talk:Rednaxela/kD-Tree
← Thread:User talk:Rednaxela/kD-Tree/Interval Heap vs MinHeap/reply (5)

Jump to navigation Jump to search

I was thinking it was the different heap... but actually turns out the heaps are approximately the same performance, with the difference being the pruning:

 - #1 Rednaxela's kd-tree (3rd gen, Interval Heap) [0.0290]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0290]
 - #3 Rednaxela's kd-tree (3rd gen, Interval Heap, Prune When Points Added) [0.0293]
 - #4 Rednaxela's kd-tree (3rd gen, Interval Heap, Avoid Growing Heap When Possible) [0.0294]
 - #5 Skilgannon's Cache-hit KDTree [0.0296]

Rednaxela (talk)‎

You do not have permission to edit this page, for the following reasons:

The action you have requested is limited to users in the group: Users.
You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page.

So the incremental difference from a larger heap is less than the cost of removing the points.

Return to Thread:User talk:Rednaxela/kD-Tree/Interval Heap vs MinHeap/reply (6).

Retrieved from "http://robowiki.net/wiki/Thread:User_talk:Rednaxela/kD-Tree/Interval_Heap_vs_MinHeap/reply_(5)#Interval_Heap_vs_MinHeap_3589"