[Olsr-dev] Improving SPF with binary heaps
Mon Oct 26 08:27:29 CET 2015
On Mon, Oct 26, 2015 at 5:27 AM, Diogo Gonçalves
> I did some tests on core and I got a initial result by now. I built on core
> a mesh network with 50, 100 and 150 nodes and 100, 200 and 300 links,
> respectively. Unfortunately my hardware isn't able to run more nodes.
> The graph (attached) shows, as expected, that avl is a little bit better
> than heap in those networks
If I read this graph right, the remove_min operation of the HEAP is
much more expensive than the remove operation of the AVL tree.
And the "insert" operation of the AVL tree is only a little bit more
expensive than the one of the HEAP.
This doesn't look good, do you have an idea why "remove" is this expensive?
More information about the Olsr-dev