<div dir="ltr"><div>you are right, the remove operation is more expensive on heap than avl.</div><div><br></div><div>Removes the min node (leftmost) of an avl with n nodes can result in 0, 1, 2 ... or log n rotations. Removes the min node (root) of the heap always result in log n rotations.</div><div><br></div><div>I can optimize the extract min operation of my heap, I wrote the code to be clean and the performance may have been a little bit decreased.</div><div><br></div><div>The question is that insert operation is executed more times than remove on dijkstra. The relax operation (_insert_into_working_tree) of avl can be a avl_remove and a avl_insert. The relax on heap is just one, it has it own relax operation. In those networks the difference of insert operation between the priority queues is small but in large networks the avl performance goes down.</div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-26 5:27 GMT-02:00 Henning Rogge <span dir="ltr"><<a href="mailto:hrogge@gmail.com" target="_blank">hrogge@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Mon, Oct 26, 2015 at 5:27 AM, Diogo Gonçalves<br>
<<a href="mailto:diogomachadogoncalves@gmail.com">diogomachadogoncalves@gmail.com</a>> wrote:<br>
> Hi,<br>
><br>
<span class="">> I did some tests on core and I got a initial result by now. I built on core<br>
> a mesh network with 50, 100 and 150 nodes and 100, 200 and 300 links,<br>
> respectively. Unfortunately my hardware isn't able to run more nodes.<br>
><br>
> The graph (attached) shows, as expected, that avl is a little bit better<br>
> than heap in those networks<br>
<br>
</span>If I read this graph right, the remove_min operation of the HEAP is<br>
much more expensive than the remove operation of the AVL tree.<br>
<br>
And the "insert" operation of the AVL tree is only a little bit more<br>
expensive than the one of the HEAP.<br>
<br>
This doesn't look good, do you have an idea why "remove" is this expensive?<br>
<span class="HOEnZb"><font color="#888888"><br>
Henning<br>
</font></span></blockquote></div><br></div>