Python heapq heappop














































Python heapq heappop



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

(Click here for full source code)

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

    def __siftup(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
        smallest=pos
        if child<len(heap) and heap[smallest]>heap[child]:
            smallest=child
        if child+1<len(heap) and heap[smallest]>heap[child+1]:
            smallest=child+1
        if smallest!=pos:
            heap[smallest],heap[pos]=heap[pos],heap[smallest]
            self.__siftup(smallest)

    def heappop(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(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' will then correct the affected branch
thus maintaining the minheap property.

Consider below example. Here '1' is poped out from minheap:


credit: MakeAGIF.com 

raw=[27, 38, 18, 17, 14]
hp=heapq(raw)
hp.heapify()
print("poped:",hp.heappop())
print("after heappop:",hp)

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


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 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