python' heapq module python' standard distribution includes heapq module that provides support for heap-based priority queues that module does not provide any priority queue classinstead it provides functions that allow standard python list to be managed as heap its model is essentially the same as our ownwith elements stored in list cells [ through [ ]based on the level-numbering indices with the smallest element at the root in [ we note that heapq does not separately manage associated valueselements serve as their own key the heapq module supports the following functionsall of which presume that existing list satisfies the heap-order property prior to the callheappush(le)push element onto list and restore the heap-order property the function executes in (log ntime heappop( )pop and return the element with smallest value from list land reestablish the heap-order property the operation executes in (log ntime heappushpop(le)push element on list and then pop and return the smallest item the time is (log )but it is slightly more efficient than separate calls to push and pop because the size of the list never changes if the newly pushed element becomes the smallestit is immediately returned otherwisethe new element takes the place of the popped element at the root and down-heap is performed heapreplace(le)similar to heappushpopbut equivalent to the pop being performed before the push (in other wordsthe new element cannot be returned as the smallestagainthe time is (log )but it is more efficient that two separate operations the module supports additional functions that operate on sequences that do not previously satisfy the heap-order property heapify( )transform unordered list to satisfy the heap-order property this executes in (ntime by using the bottom-up construction algorithm nlargest(kiterable)produce list of the largest values from given iterable this can be implemented to run in ( log ntimewhere we use to denote the length of the iterable (see exercise - nsmallest(kiterable)produce list of the smallest values from given iterable this can be implemented to run in ( log ntimeusing similar technique as with nlargest