stl heap question: restoring heap validinty after changing 1 element

Discussion in 'C++' started by viki, Jun 24, 2008.

  1. viki

    viki Guest

    I have vector 'vec' of integers which was made into valid heap using
    std::make_heap().

    Then we change value of a single element vec[k], like: vec[k] =
    new_value;

    Now this makes vec not a valid heap.

    Heaps have simple algorithm that restores "heap validity" in O(log
    N)after one element was changed, knowing index of changed element.

    But I cannot find this function in stl.

    Which stl function restores my heap vaidity in O(log N) after single
    element change, given known index k of changed element ?

    Thanks
    vikimun
     
    viki, Jun 24, 2008
    #1
    1. Advertising

  2. Re: stl heap question: restoring heap validinty after changing 1element

    On 2008-06-24 21:14, viki wrote:
    > I have vector 'vec' of integers which was made into valid heap using
    > std::make_heap().
    >
    > Then we change value of a single element vec[k], like: vec[k] =
    > new_value;
    >
    > Now this makes vec not a valid heap.
    >
    > Heaps have simple algorithm that restores "heap validity" in O(log
    > N)after one element was changed, knowing index of changed element.
    >
    > But I cannot find this function in stl.
    >
    > Which stl function restores my heap vaidity in O(log N) after single
    > element change, given known index k of changed element ?


    None that I can find, but it might be possible that make_heap takes no
    more than O(log N) if the range is almost heap (you'll have to research
    this yourself). If you really need such functionality you have to
    implement it yourself, given that the algorithms are well-known it
    should not be too hard.

    --
    Erik Wikström
     
    Erik Wikström, Jun 24, 2008
    #2
    1. Advertising

  3. viki

    Arash Partow Guest

    Re: stl heap question: restoring heap validinty after changing 1element

    I believe std::push_heap is what you're looking for:

    http://www.sgi.com/tech/stl/push_heap.html

    Resulting in a three step process:

    vec.erase(vec.begin() + k);
    vec.push_back(new_value);
    std::push_heap(vec.begin(),vec.end());



    Arash Partow
    __________________________________________________
    Be one who knows what they don't know,
    Instead of being one who knows not what they don't know,
    Thinking they know everything about all things.
    http://www.partow.net


    On Jun 25, 5:14 am, viki <> wrote:
    > I have vector 'vec' of integers which was made into valid heap using
    > std::make_heap().
    >
    > Then we change value of a single element vec[k], like: vec[k] =
    > new_value;
    >
    > Now this makes vec not a valid heap.
    >
    > Heaps have simple algorithm that restores "heap validity" in O(log
    > N)after one element was changed, knowing index of changed element.
    >
    > But I cannot find this function in stl.
    >
    > Which stl function restores my heap vaidity in O(log N) after single
    > element change, given known index k of changed element ?
    >
    > Thanks
    > vikimun
     
    Arash Partow, Jun 25, 2008
    #3
  4. Re: stl heap question: restoring heap validinty after changing 1element

    On 2008-06-25 04:32, Arash Partow wrote:
    > On Jun 25, 5:14 am, viki <> wrote:
    >> I have vector 'vec' of integers which was made into valid heap using
    >> std::make_heap().
    >>
    >> Then we change value of a single element vec[k], like: vec[k] =
    >> new_value;
    >>
    >> Now this makes vec not a valid heap.
    >>
    >> Heaps have simple algorithm that restores "heap validity" in O(log
    >> N)after one element was changed, knowing index of changed element.
    >>
    >> But I cannot find this function in stl.
    >>
    >> Which stl function restores my heap vaidity in O(log N) after single
    >> element change, given known index k of changed element ?


    Please do not top-post, and do not quota signatures.

    > I believe std::push_heap is what you're looking for:
    >
    > http://www.sgi.com/tech/stl/push_heap.html
    >
    > Resulting in a three step process:
    >
    > vec.erase(vec.begin() + k);
    > vec.push_back(new_value);
    > std::push_heap(vec.begin(),vec.end());


    Is vec guaranteed to still be a valid heap if you erase an arbitrary
    element in the middle of it? If not you can not use this method since it
    assumes that all elements but the last are a heap.

    --
    Erik Wikström
     
    Erik Wikström, Jun 25, 2008
    #4
  5. viki

    Arash Partow Guest

    Re: stl heap question: restoring heap validinty after changing 1element

    Erik you could be right, I believe there is no guarantee. I revise my
    suggestion, it now involves re-pushing all the elements after the
    erased element. This would be of O(logn) complexity.

    typeof(v)::iterator it = v.erase(v.begin() + k);
    while(v.end() != it) { std::push_heap(v.begin(),it++); }
    v.push_back(new_value);
    std::push_heap(v.begin(),v.end());
    ::assert(std::is_heap(v.begin(),v.end()));


    Arash Partow
    __________________________________________________
    Be one who knows what they don't know,
    Instead of being one who knows not what they don't know,
    Thinking they know everything about all things.
    http://www.partow.net

    On Jun 26, 1:59 am, Erik Wikström <> wrote:
    >
    > Is vec guaranteed to still be a valid heap if you erase an arbitrary
    > element in the middle of it? If not you can not use this method since it
    > assumes that all elements but the last are a heap.
    >
    > --
    > Erik Wikström
     
    Arash Partow, Jun 26, 2008
    #5
  6. viki

    Ivan Novick Guest

    Re: stl heap question: restoring heap validinty after changing 1element

    On Jun 24, 12:14 pm, viki <> wrote:
    > I have vector 'vec' of integers which was made into valid heap using
    > std::make_heap().
    >
    > Then we change value of  a single element vec[k], like:  vec[k] =
    > new_value;
    >
    > Now this makes vec not a valid heap.
    >
    > Heaps have simple algorithm that restores "heap validity" in O(log
    > N)after one element was changed, knowing index of changed element.
    >
    > But I cannot find this function in stl.
    >
    > Which stl  function restores my heap vaidity in O(log N) after single
    > element change, given known index k of changed element ?
    >
    > Thanks
    > vikimun


    If you are trying to use a std::vector to be a heap, could you use the
    STL priority queue? I thought the priority queue class was
    essentially a heap.

    Ivan Novick
    http://www.mycppquiz.com/
     
    Ivan Novick, Jun 26, 2008
    #6
  7. Re: stl heap question: restoring heap validinty after changing 1element

    On 2008-06-26 23:31, Ivan Novick wrote:
    > On Jun 24, 12:14 pm, viki <> wrote:
    >> I have vector 'vec' of integers which was made into valid heap using
    >> std::make_heap().
    >>
    >> Then we change value of a single element vec[k], like: vec[k] =
    >> new_value;
    >>
    >> Now this makes vec not a valid heap.
    >>
    >> Heaps have simple algorithm that restores "heap validity" in O(log
    >> N)after one element was changed, knowing index of changed element.
    >>
    >> But I cannot find this function in stl.
    >>
    >> Which stl function restores my heap vaidity in O(log N) after single
    >> element change, given known index k of changed element ?
    >>
    >> Thanks
    >> vikimun

    >
    > If you are trying to use a std::vector to be a heap, could you use the
    > STL priority queue? I thought the priority queue class was
    > essentially a heap.


    The problem with the priority_queue is that it does not allow random
    access of elements, it provides only push(), pop(), and top().

    --
    Erik Wikström
     
    Erik Wikström, Jun 28, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. HANM
    Replies:
    2
    Views:
    734
    Joseph Kesselman
    Jan 29, 2008
  2. Michal Slocinski

    Heap dump file size vs heap size

    Michal Slocinski, Mar 25, 2008, in forum: Java
    Replies:
    1
    Views:
    751
    GArlington
    Mar 25, 2008
  3. Jarrick Chagma
    Replies:
    28
    Views:
    1,081
    Martin Gregorie
    May 27, 2009
  4. Marcelo Alvim
    Replies:
    1
    Views:
    111
  5. ed_spain

    Restoring OTHER form field after submit

    ed_spain, Sep 23, 2005, in forum: Javascript
    Replies:
    3
    Views:
    267
    Evertjan.
    Sep 23, 2005
Loading...

Share This Page