Hi,
In article <199910211449.QAA27131@valerie.inf.elte.hu>,
  sarlos@inf.elte.hu wrote:

> Does anyone know why there is no key_decrease operation for STL heaps?

To efficiently change the key of an item stored in a heap you have to
keep track of this item somehow. This can by done by some sort of a
pointer or an index but this involves extra maintainance which is quite
costly. Thus, it was choosen to use a priority queue without this
feature.

I have implemented a heap of heaps which are available from
<http://www.boost.org/>. These include different cost trade-offs and
most of these heaps provide operations to change the key of objects
stored in the heap.
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,

Does anyone know why there is no key_decrease operation for STL heaps?

Thanx,


Tamas Sarlos, CS stud., Budapest, Hungary
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi Tamas,

I was not involved with the design of the STL heap functions, but I bet the
following guess
is correct:

I will assume by key_decrease you meant something like:
key_decrease(H.begin(), H.end(), x, k)
that is, decrease the key for node x to k in heap H. (as per Cormen et. all)

The problem is that there is no notion of "node" separate from key
in an STL heap (which is just some container of keys). So it does not
make sense to define a key_decrease heap function, as heaps are defined in
STL.
That is not to say that a heap class that understands both "nodes" and
"keys" would not
be useful. I've implemented such a heap. Perhaps one reason this kind of
heap did not make it into the standard is that it is a bit more complicated.
One needs
an auxiliary data structure (usually an array) to be able to find
where a particular node is at any given time in the heap. This
constant-time lookup is needed to implement key_decrease
efficiently. Also perhaps this kind of heap has limited applicability.
Useful for dijkstra's single-source and some other graph algorithms,
but anything else?

Hope this helps!

Jeremy

sarlos@inf.elte.hu wrote:

> Hi,
>
> Does anyone know why there is no key_decrease operation for STL heaps?
>
> Thanx,
>
> Tamas Sarlos, CS stud., Budapest, Hungary
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]