<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 11 July 2015 at 03:34, 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span>On Sat, Jul 11, 2015 at 12:43 AM, Saulo Queiroz <<a href="mailto:ssaulojorge@gmail.com" target="_blank">ssaulojorge@gmail.com</a>> wrote:<br>
> Hi Henning,<br>
> I've supervised the work of Diogo.<br>
> Regarding you first question, response is no. Not all procedures are used.<br>
> Diogo just listed in .h all classical procedures of a binary heap but only<br>
> the ones required by Dijkstra are implemented. The other are there just<br>
> as a reminder, but he can clean .h,  No problem.<br>
<br>
</span>I would suggest moving everything that is "internal" to a static<br>
function... this makes it easier for new users of the API to<br>
understand what they need because they only have to look at the header<br>
file.<br>
<span><br></span></blockquote><div>OK. <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span>
> Regarding the second question:  heap_extract_min is the procedure you asked<br>
> about.<br>
> Note however that the idea is to replace AVL only for Dijkstra and keeping<br>
> AVL there for other stuff. ok?<br>
<br>
</span>I would like to have this as a generic API, so I am looking which<br>
basic functions we have, we still need or we cannot get.<br>
<br>
Basics for both lists and AVL trees in OONF (which is the base of OLSRv2) is<br>
- init<br>
- insert<br>
- remove<br>
- get(key)<br>
- get_first<br>
- get_last<br>
<br>
and a good way to iterate over the elements of the tree/list (which<br>
would enable me to write iterator macros like the ones in<br>
<a href="http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315" rel="noreferrer" target="_blank">http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315</a><br>
).<br>
<br>
Can we have the same functions for a binary heap? </blockquote><div>It
 is possible but i think few procedures don't sound reasonable because binary heaps <br>are Priority Queues (PQs) by nature being different from the typical data structures. <br>In general, one employs priority queues when 
all items are expected to leave the structure until the end of the 
execution of a procedure  (what is very usual in the so-called "greedy 
algorithms" like Dijkstra). In "normal" data structures, there is no 
problem if an item stay in the structure "forever". In PQs the earlier 
an item leaves the structure, the better (to it) because this means it will be 
served first (in case of Dijkstra this means the shortest path 
computation ends for the extracted item). <br>In this context, functions like get(key) doesn't sound important because focus goes to the priority assigned to the items not to the key values. Perhaps we should start discussing an API for PQs since other can be implemented like Fibonacci, Binomial, etc.<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
If yes, it makes sense to disallow AVL trees with overlapping keys<br>
(which is a parameter in avl_init at the moment) and tell the<br>
developers "use a binary heap instead for this case".<br></blockquote><div>Wherever AVL has been used as a priority queue (as I just explained) it can be replaced by binary heaps. Other scenarios need to be analyzed.<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
The heap (because its different than AVL) might of course have a few<br>
more functions, like the "modify key later" functions you have. Its<br>
just about the same "basic set".<br>
<span><font color="#888888"><br>
Henning<br>
</font></span></blockquote></div><br><br clear="all"><br>-- <br><div>Saulo Jorge bq<br>-<br>"In theory, there is no difference between practice and theory, in practice there is"<br>-- Someone</div>
</div></div>