[Olsr-dev] Improving SPF with binary heaps
Sun Jul 12 09:26:00 CEST 2015
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)
>> - 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
>> 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
> 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".
so its more like
- 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?
More information about the Olsr-dev