Python heapq _heappop_max














































Python heapq _heappop_max



(<-Home)
_heappop_max will pop out the topmost item from heap maintaining maxheap property.

(Click here for full source code)

    #This snippet is from heapq class. 'self' refers to heap object

    def __siftup_max(self,pos):
        """adjust item at pos to its correct position 
        and following sub tree, if misplaced"""
        heap=self.__heap
        child=2*pos+1 # left child
        largest=pos
        if child<len(heap) and heap[largest]<heap[child]:
            largest=child
        if child+1<len(heap) and heap[largest]<heap[child+1]:
            largest=child+1
        if largest!=pos:
            heap[largest],heap[pos]=heap[pos],heap[largest]
            self.__siftup_max(largest)

    def _heappop_max(self):
        """remove item from the heap maintaining heap property"""
        heap=self.__heap
        lastitem=heap.pop()
        if heap:
            topmost=heap[0]
            heap[0]=lastitem
            self.__siftup_max(0)
            return topmost
        return lastitem

For poping, the topmost element is replaced by the last item of heap and topmost
item will be returned at last. '__siftup_max' will then correct the affected branch
thus maintaining the maxheap property.

Consider below example. Here '45' is poped out from maxheap:



## Another Example
raw=[27, 38, 18, 17, 14]
hp=heapq(raw)
hp._heapify_max()
print("poped:",hp._heappop_max())
print("after heappop:",hp)

>>poped: 38
>>after heappop: [27, 17, 18, 14]

More Articles of mradul tiwari:

Name Views Likes
Python heapq heappush 557 1
Image Recognition program using Python 811 0
Python heapq _heappush_max 1873 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 913 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 472 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