[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

On Mon, Oct 26, 2015 at 5:27 AM, Diogo Gonçalves
<(spam-protected)> wrote:
> Hi,
>
> 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?

Henning