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