[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

Hi,

just that I understand it right... you can normally only access "one
end" of the PQ easily... so if you want to get a "maximum queue" you
need some code-change... or you just have to negate the key before
inserting an element.

Henning

On Sun, Jul 12, 2015 at 2:56 PM, Saulo Queiroz <(spam-protected)> wrote:
> 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.
> ....
>
> the lower the priority number associated
>
> Em 12/07/2015 04:26, "Henning Rogge" <(spam-protected)> escreveu:
>>
>> 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