Python heapq _heappush_max














































Python heapq _heappush_max



(<-Home)
_heappush_max(item) will insert an 'item' on the heap maintaining maxheap property.
Look at the code snipet below:
(click here for full source code)

  # This snipet is from heapq class. 'self' refers to heap object.
def _heappush_max(self,item):
        """push item on the heap maintaining heap property"""
        heap=self.__heap # object "self.__heap" is assigned to heap for simplicity  
        heap.append(item) # item is inserted at the end of list
        self.__siftdown_max(0,len(heap)-1) # modify list to maintain heap property

 def __siftdown_max(self,start,end):
        """correct a heap by placing element at end to its correct place"""
        heap=self.__heap
        newitem=heap[end]
        while end>start:
            parentpos=(end-1)>>1
            parent=heap[parentpos]
            if newitem>parent:
                heap[end]=parent
                end=parentpos
                continue
            break
        heap[end]=newitem

The newly added item should always be appended at the end of current heap. Than,
adjust the heap to maintain the maxheap property as follow:
For the newly inserted element, compare it with its parent. Move down parent at each
node until find the correct place for new element. Insert element at this location.

Consider below example. Here 39 is inserted on maxheap.


##Another Example

raw=[27, 38, 18, 17, 14]
hp=heapq(raw)
hp._heapify_max()
hp._heappush_max(15)
print("after heappush:",hp)

>>after heappush: [38, 27, 18, 17, 14, 15]

More Articles of mradul tiwari:

Name Views Likes
Python heapq heappush 557 1
Image Recognition program using Python 811 0
Python heapq _heappush_max 1874 0
Python heapq _heappushpop_max 727 0
Python heapq _heapreplace_max 431 0
python heapq introduction 469 1
Python heapq nlargest 701 0
Python heapq Full SourceCode 914 1
Translating language using Google API and Python 460 1
Python heapq _heapify_max 890 0
Countdown Timer in Python 910 1
Python heapq heappushpop 430 0
Python heapq heapify 310 0
Python heapq heapreplace 414 0
Python Builtin filter 310 0
Python heapq nsmallest 296 0
Python heapq heappop 473 1
Python heapq _heappop_max 930 0
Python Manual Exception handling 330 0
General Questions on Heap 270 0
Python heapq merge 685 0
Python functools reduce 302 0
Getting text from image using Python and ML 474 0
Converting Voice to Text 343 0
python shutil introduction 271 0

Comments