Proof that this assertion about heaps is true

smangano_at_ureach.com
Date: 10/18/04

  • Next message: Mike Atkinson: "CATS'05 Accepted Papers" 
    Date: 18 Oct 2004 13:27:19 -0700

    Hi all,

    I am using a binary min heap in an effort to optimize a particular
    piece of code whose details I believe are irrelevant to the question I
    have. However, in a portion of this code I need to modify an arbitrary
    element of the heap in such a way that I can guarantee the following
    is true:

    After modifying the heap, it is certain that the value of the element
    modified is less than all other values in the heap. In other words,
    this new element belongs at the front of the heap.

    I will use C++ STL terminology, but what I am really after is if this
    is true in general for heaps.

    I know then that if iModIndex is the index of the item changed and vec
    is the heap then:

    make_heap(vec.begin(), vec.end(), greater<int>()); //greater<int>() is
    a comparison functor needed to make this a min heap.

    will definitly restore the heap by definition. However, given the
    knowledge of the change made I belive it would be sufficient to say:

    make_heap(vec.begin(), vec.begin() + iModIndex + 1, greater<int>()) ;

    However, I also believe, and this is what I would like to prove, that
    it is only necessary to say:

    push_heap(vec.begin(), vec.begin() + iModIndex + 1, greater<int>()) ;

    I apologize for using STL specific terminology. I really mean this to
    be a general question about the properties of heaps and even if you
    are not familiar with STL, I hope my intensions are fairly clear.

    I have written a program that creates random heaps of sizes 4 thur
    1000 and verified that this always works for every position in the
    vector but obviously that is not a proof!

  • Next message: Mike Atkinson: "CATS'05 Accepted Papers"

    Relevant Pages

    • Re: Python and STL efficiency
      ... efficiency of python and STL. ... you are benching heap allocations and of course heap fragmentation. ...
      (comp.lang.python)
    • Re: Question about STL containers in multithreaded environment
      ... Everything is protected from simultaneous accesses. ... It is possible that failure is caused not by STL itself but by broken ... You have broken your heap before and STL just fails to ...
      (comp.programming.threads)
    • Re: sharing STL object across process using shared memory
      ... compatibility. ... Each process has to be compiled with the same version of STL. ... data in the heap of process. ... So if you just copy stl object into another ...
      (microsoft.public.vc.stl)
    • Re: Proof that this assertion about heaps is true
      ... assuming the particular implementation is a binary heap and the ... I suppose to guarantee I am okay I'll have to write my own heap ... >> will definitly restore the heap by definition. ... > the requirements of the standard. ...
      (comp.theory)