std::heap update

It is true that was STL gives you is just push_heap() and pop_heap() to manipulate heaps. There is no way to update the heap. Since heap is commonly used for priority queues I expected it to have update functionality implemented. I find it quite restrictive to have a priority queue where the priority of an item can't change!

Some time ago I implemented some templetized update_heap() function. The implementation is such that blends smoothly with the STL. The syntax of update_heap() is :

void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval)

or if you need to supply a compare functor :

void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CPred pred)

For my blog post about this code check this link.

/**************************************************************************
===========================================================================
Copyright (C) 2000-2005 Harry Kalogirou

This file is part of Sylphis3D source code.

This program is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
**************************************************************************/

#ifndef _HEAP_EXTRA_
#define _HEAP_EXTRA_

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _up_heap(CRanIt first, CRanIt last, CRanIt pos, CDiff *, CType *, CPred pred){	
    CDiff parent = (pos - first - 1) / 2;
    CDiff index = pos - first;
    CType mov = *pos;

    while(index > 0 && pred(*(first + parent),mov) ){
        *(first + index) = *(first + parent);
        index = parent;
        parent = (parent - 1) / 2;
    }

    if(index != pos - first)
        *(first + index) = mov;
}

template<class CRanIt> inline
void up_heap(CRanIt first, CRanIt last, CRanIt pos)
{	
    if (first == last)
        return;

    _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CPred> inline
void up_heap(CRanIt first, CRanIt last, CRanIt pos, CPred pred)
{	
    if (first == last)
        return;

    _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred );
}

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _down_heap(CRanIt first, CRanIt last, CRanIt pos, CDiff *, CType *, CPred pred){	
    CType mov = *pos;
    CDiff index = pos - first;
    CDiff left = 2 * index + 1;
    CDiff right = 2 * index + 2;
    CDiff len = last - first;
    CDiff largest;
   
    while(left < len){
        if( right < len && pred(*(first + left), *(first + right)) ){
            largest = right;
        } else {
            largest = left;
        }
        if( pred(mov, *(first + largest)) ){
            *(first + index) = *(first + largest);
            index = largest;
            left = 2 * index + 1;
            right = 2 * index + 2;
        } else {
            break;
        }
    }

    if(index != pos - first)
        *(first + index) = mov;
}

template<class CRanIt> inline
void down_heap(CRanIt first, CRanIt last, CRanIt pos)
{	
    if (first == last)
        return;

    _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CPred> inline
void down_heap(CRanIt first, CRanIt last, CRanIt pos, CPred pred)
{	
    if (first == last)
        return;

    _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred );
}

template<class CRanIt, class CDiff, class CType, class CPred> inline
void _update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CDiff *, CPred pred){	
    CDiff index = pos - first;
    CDiff parent = ( index - 1 ) / 2;
    *(first + index) = newval;
    if(index > 0 && pred(*(first + parent), newval)){
        _up_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred);
    } else {
        _down_heap(first, last, pos, _Dist_type(first), _Val_type(first), pred);
    }
}


template<class CRanIt, class CType> inline
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval)
{	
    if (first == last)
        return;

    _update_heap(first, last, pos, newval, _Dist_type(first), std::less< CRanIt::value_type >() );
}

template<class CRanIt, class CType, class CPred> inline
void update_heap(CRanIt first, CRanIt last, CRanIt pos, CType *newval, CPred pred)
{	
    if (first == last)
        return;

    _update_heap(first, last, pos, newval, _Dist_type(first),  pred );
}

#endif

Hi,

It is indeed suprising to see that STL doesn't provide an algorithm to adjust one value of the heap. OTOH, i never needed it before Luckely, the STL is set up as such that it can easily be expanded. Though if you do, I suggest you stick to standard STL functions. The problem in this case is _Dist_type and _Val_type. Although probably provided by the STL you're using, these are by no means standard provided functions. So, if you try to use it with another implementation, it may possible break. AFAIK, the best change you have is to use iterator_traits to get these values. I also wondered why you pass newval by pointer to update_heap. a constant reference seems more suitable to me, or why not - to use the same spirit as the other heap functions - let the client update the iterator before calling update_heap. (and on the nitpicking side: it's best to avoid leading underscores )

Bramz

Originally Posted by bramz

(and on the nitpicking side: it's best to avoid leading underscores )

Well, the only reason I can think of is that _[A-Z][A-Za-z0-9_]* and __[A-Za-z0-9_]* are reserved for implementation. So functions like _up_heap shouldn't cause a problem. The header guard _HEAP_EXTA_, however, might

/END NITPICKING

.oisyn,

you might check out section 17.4.3.1.2 of the standard plus its footnote to see that _[A-Za-z0-9_]* is reserved for names in global and ::std namespace as well. Since he hasn't put his functions in any namespace, that means ... exactly

Besides, __[A-Za-z0-9_]* doesn't cover things like foo__bar which is reserved as well ... in any namespace

Bramz

I stand corrected, I must've wrongly interpreted that paragraph the last time I read it.

and it looks like your virus is spreading

Originally Posted by .oisyn

and it looks like your virus is spreading

Yes, it's a rather nasty one ...