[Olsr-dev] Improving SPF with binary heaps
Mon Jul 13 08:12:06 CEST 2015
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.
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)>
>> >> 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".
>> 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?
More information about the Olsr-dev