Priority Queues

By default, the heap implementation in Python creates a min-heap. This means heappop returns the smallest element.

# importing "heapq" to implement heap queue
import heapq
# initializing list
li = [5, 7, 9, 1, 3]
# using heapify to convert list into heap
# Transform list x into a heap, in-place, in linear time.
heapq.heapify(li)
# printing created heap
print ("The created heap is : ",end="")
print (list(li))
# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li,4)
# printing modified heap
print ("The modified heap after push is : ",end="")
print (list(li))
# using heappop() to pop smallest element (min-heap)
print ("The popped and smallest element is : ",end="")
print (heapq.heappop(li))
'''
Output:
The created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1
'''

Source: http://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

Note: To create a max-heap, we can invert the values (e.g. 5 becomes -5) before placing in the heap.

Heap Sort#

# note: this implementation is not stable
def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]

Source: https://docs.python.org/3.6/library/heapq.html