<p dir="ltr">Yes with a little remark to functions of type first/last. We have two kinds o PQs: MINimum and MAXimum. In min PQs, item priority means being associated to low values (case of Dijkstra). In this case, get_first would return the item with lowest number but get_last doesn't make sense. Similar situation happens for max priority queues. <br>
....</p>
<p dir="ltr">the lower the priority number associated</p>
<div class="gmail_quote">Em 12/07/2015 04:26, "Henning Rogge" <<a href="mailto:hrogge@gmail.com">hrogge@gmail.com</a>> escreveu:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Jul 12, 2015 at 3:48 AM, Saulo Queiroz <<a href="mailto:ssaulojorge@gmail.com">ssaulojorge@gmail.com</a>> wrote:<br>
>> Basics for both lists and AVL trees in OONF (which is the base of OLSRv2)<br>
>> 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>
>><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?<br>
><br>
> It is possible but i think few procedures don't sound reasonable because<br>
> binary heaps<br>
> are Priority Queues (PQs) by nature being different from the typical data<br>
> structures.<br>
> In general, one employs priority queues when all items are expected to leave<br>
> the structure until the end of the execution of a procedure (what is very<br>
> usual in the so-called "greedy algorithms" like Dijkstra). In "normal" data<br>
> structures, there is no problem if an item stay in the structure "forever".<br>
<br>
Okay,<br>
<br>
so its more like<br>
<br>
- insert<br>
- remove first/last<br>
- get first/last<br>
<br>
Maybe even with get and remove combined into the same function, so<br>
that you can get the first/last element of the heap and remove it.<br>
<br>
Does this make more sense?<br>
<br>
Henning<br>
</blockquote></div>