[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

On Sun, Jul 12, 2015 at 3:48 AM, Saulo Queiroz <(spam-protected)> wrote:
>> Basics for both lists and AVL trees in OONF (which is the base of OLSRv2)
>> is
>> - init
>> - insert
>> - remove
>> - get(key)
>> - get_first
>> - get_last
>>
>> and a good way to iterate over the elements of the tree/list (which
>> would enable me to write iterator macros like the ones in
>>
>> http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315
>> ).
>>
>> Can we have the same functions for a binary heap?
>
> It is possible but i think few procedures don't sound reasonable because
> binary heaps
> are Priority Queues (PQs) by nature being different from the typical data
> structures.
> 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".

Okay,

so its more like

- insert
- remove first/last
- get first/last

Maybe even with get and remove combined into the same function, so
that you can get the first/last element of the heap and remove it.

Does this make more sense?

Henning