heapq_del.py: heapq.py + heapchange heapdel

heapq_del.py

""" heapq_del.py: heapq.py + heapchange heapdel
    see http://docs.python.org/2/library/heapq.html
    c heap* but python _siftup _siftdown, slow
"""
    # cf. class Aheapq: heap --> A[ Arecs with .val .heappos ... ]

from heapq import heappush, heappop, heapify, heapreplace, _siftup, _siftdown
    # http://docs.python.org/2/library/heapq.html
    # https://github.com/python/cpython/blob/master/Modules/_heapqmodule.c
    # (note _siftup --> leaves, _siftdown --> root
    # upside down from the usual diagrams with root at top, leaves bottom)

__version__ = "2014-04-22 apr denis"
_Test = 0

#...............................................................................
def heapchange( heap, pos ):
    """ heap[pos] = new val  > or < old val
        heapchange( heap, pos ): fix heap, bubble up or down
    """
    val = heap[pos]
    if _Test >= 2:
        print "heapchange pos %d  %s" % (pos, np.array(heap))
    parentpos = (pos - 1) >> 1
    if pos > 0  and heap[parentpos] > val:
        _siftdown( heap, 0, pos )  # --> root
    else:
        l = 2*pos + 1
        r = 2*pos + 2
        n = len(heap)
        if (l < n  and heap[l] < val) \
        or (r < n  and heap[r] < val):  # cmp_lt
            _siftup( heap, pos )  # --> leaf

def heapdel( heap, pos ):
    """ del heap[pos]: val -inf, sift to root, pop """
    if _Test >= 2:
        print "heapdel %d  %s" % (pos, np.array(heap))
    heap[pos] = -1e500  # - inf
    _siftdown( heap, 0, pos )  # --> root
    heappop( heap )


#-------------------------------------------------------------------------------
if __name__ == "__main__":
    from copy import copy
    import sys
    import numpy as np

    nn = [10, 100, 1000]
    _Test = 1
    seed = 0

        # run this.py a=1 b=None c=[3] 'd = expr' ...  in sh or ipython
    for arg in sys.argv[1:]:
        exec( arg )
    np.set_printoptions( 2, threshold=100, edgeitems=10, linewidth=100, suppress=True )
    np.random.seed(seed)

#...............................................................................
    def testheap( heap ):
        for pos in range( 1, len(heap) ):
            parentpos = (pos - 1) >> 1
            if heap[parentpos] > heap[pos]:
                print "not heap: %d %d  %s " % (parentpos, pos, np.array(heap) )

    def huffman( heap, nbig=1 ):
        """ merge 2 smallest, loop; see wikipedia Huffman_coding """
        for jmerge in xrange( len(heap) ):
            if len(heap) <= nbig:  break
            hmin = heappop( heap )
            heap[0] += hmin 
            heapchange( heap, 0 )
        return heap

    def changes( heap, randominc ):
        """ random changes to heap """
        heap0 = copy(heap)
        for j, r in enumerate( randominc ):
            heap = copy( heap0 )
            heap[j] += r
            heapchange( heap, j )
            testheap( heap )

    def deletes( heap ):
        """ delete each heap[j] """
        heap0 = copy(heap)
        for j in range( len(heap) ):
            heap = copy( heap0 )
            heapdel( heap, j )
            testheap( heap )

#...............................................................................
    for n in nn:
        n = int(n)
        randexp = (np.random.exponential( size=n ) * 100) .round().astype(int)

        def makeheap( vals=randexp ):
            heap = vals.tolist()
            heapify( heap )
            return heap

        heap = makeheap()
        print "\n-- random exp  n %g: init heap %s" % (n, np.array(heap))

        print "deletes --"
        deletes( heap )

        print "changes --"
        heap = makeheap()
        changes( heap, np.random.randint( -100, 100, n ))

        print "huffman --"
        heap = makeheap()
        heap = huffman( heap, nbig=5 )