<div dir="ltr"><div><div>Hi Henning,<br></div>I've supervised the work of Diogo.<br></div><div>Regarding you first question, response is no. Not all procedures are used.<br></div><div>Diogo just listed in .h all classical procedures of a binary heap but only<br></div><div>the ones required by Dijkstra are implemented. The other are there just<br></div><div>as a reminder, but he can clean .h,  No problem.<br></div><div><br></div><div>Regarding the second question:  heap_extract_min is the procedure you asked about.<br></div><div>Note however that the idea is to replace AVL only for Dijkstra and keeping AVL there<br></div><div>for other stuff. <br></div><div>ok?<br><br></div><div>best regard<br></div><br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On 10 July 2015 at 08:17, Henning Rogge <span dir="ltr"><<a href="mailto:hrogge@gmail.com" target="_blank">hrogge@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Thu, Jul 9, 2015 at 9:32 PM, Diogo Gonçalves<br>
<<a href="mailto:diogomachadogoncalves@gmail.com">diogomachadogoncalves@gmail.com</a>> wrote:<br>
</span><div><div class="h5">> Hi all,<br>
><br>
> I've studied performance of olsrd's SPF under different priority queues.<br>
> We find it quite surprising that in olsrd Dijkstra is based on AVL instead<br>
> of binary heaps. Different from binary heaps, AVL is not originally<br>
> intendend<br>
> as a priority queue. To achieve O(log n) performance, AVL requires nodes<br>
> with<br>
> unique key values, which is not reasonable for a priority queues since<br>
> different<br>
> nodes can have the same priority. In fact, in the olsrd's SPF, nodes with<br>
> same<br>
> priority are put into a list. Then decrase-key procedure can be O(n) in some<br>
> cases<br>
> and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most<br>
> popular<br>
> priority queue for Dijkstra, achieving O(n*logn) regardless nodes have the<br>
> same priority.<br>
> I put in my github an initial version of binary heaps (BH) for olsrd [1].<br>
> With traces from a 200-node mesh [2], Dijkstra-BH behaved very similar to<br>
> Dijkstra-AVL.<br>
> However, from 800 nodes, Dijkstra-BH drammatically outperformed<br>
> Dijkstra-AVL.<br>
> Comments, improvements and bugfixes are welcome,<br>
<br>
</div></div>Hi,<br>
<br>
I had a short look at "heap.h"... are all of these functions called<br>
from the user of the heap, even things like "swap_left" and<br>
"swap_right" ?<br>
<br>
I am also quite unsure what I use "heap_decrease_key" and "heap_increase_key".<br>
<br>
How do I remove things from a heap (I don't see a remove function) ?<br>
<span class="HOEnZb"><font color="#888888"><br>
Henning<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
--<br>
Olsr-dev mailing list<br>
<a href="mailto:Olsr-dev@lists.olsr.org">Olsr-dev@lists.olsr.org</a><br>
<a href="https://lists.olsr.org/mailman/listinfo/olsr-dev" rel="noreferrer" target="_blank">https://lists.olsr.org/mailman/listinfo/olsr-dev</a></div></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature">Saulo Jorge bq<br>-<br>"In theory, there is no difference between practice and theory, in practice there is"<br>-- Someone</div>
</div>