Heap

Heapq is a min heap, the smallest item is returned by pop

import heapq
list = [5, 7, 9, 1, 3]
heapify(list) # O(n)
# [1, 3, 9, 7, 5]

Create Empty Heap

heap = []
heapq.heapify(heap)

Add

heapq.heappush(heap,4) # push element onto heap
# [1, 3, 4, 7, 5, 9]

Add List

> listA = [2, 'a', 'a']
> listB = [3, 'b', 'b']
# 2 will be used in the heap evaluation
> heapq.heappush(heap, listA)
> heapq.heappush(heap, listB)
> heapq.heappop(heap)
[2, 'a', 'a']

Peek Smallest

heap[0]

Pop

heapq.heappop(heap) # pop smallest element

Push Pop

heapq.heappushpop(heap, ele)
# pushes to the heap and the pops the smallest element
# combines the functions into 1

Pop Push

heapq.heapreplace(heap, ele)
# first pop then push the element
# returns the smallest element on the heap before pushing the new element

K Smallest

# return the k largest elements from heap
heapq.nlargest(k, heap)

K Largest

# return the k smallest elements from heap
heapq.nsmallest(k, heap)

Merge

heapq.merge(*iterables, key=None, reverse=False)

Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.

Has two optional arguments which must be specified as keyword arguments.

key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).

reverse is a boolean value. If set to True, then the input elements are merged as if each comparison were reversed.

> a = [2, 3, 6, 7, 8]
> b = [0, 1, 5, 9, 11]
> list(heapq.merge(a, b))
[0, 1, 2, 3, 5, 6, 7, 8, 9, 11]

Examples

Heap Sort

> def heapsort(iterable):
     h = []
     for value in iterable:
         heappush(h, value)
     return [heappop(h) for i in range(len(h))]

> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Using Tuples

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

Max Heap

# Creating empty heap
> heap = []
> heapify(heap)

# Adding items to the heap using heappush
# function by multiplying them with -1
> heappush(heap, -1 * 10)
> heappush(heap, -1 * 30)
> heappush(heap, -1 * 20)
> heappush(heap, -1 * 400)

> -1 * heap[0]
400