[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

Yes,
something like 1/priority_value (for instance) might work.

On 13 July 2015 at 03:12, Henning Rogge <(spam-protected)> wrote:

> 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
>



-- 
Saulo Jorge bq
-
"In theory, there is no difference between practice and theory, in practice
there is"
-- Someone
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150713/37c02929/attachment.html>