Data Structures

Data Structures

A quick reference sheet for different data structures and possible python/go/c implementation of said data structures.

Heaps

A heap is a complete binary tree where all children of any node have a greater value than the node itself.

A complete binary tree is a type of binary tree where all levels are fully filled except possibly the last level, which is filled from left to right.

An example of a heap:

    0
   / \
  1   2
 / \  /
3  4  6

Heaps in Python

from heapq import heapify, heappush, heappop, nlargest

# convert array to heap O(n lg n)
x = [1,2,3,4]
heapify(x)

The heapify function turns an existing array into a heap structure. It does this in-place, and does not return the heap. We do not have to call heapify on an empty array as it would no do anything.

# push elements onto the heap O(lg n)
heappush(x, 2)
heappush(x, 15)
heappush(x, 20)

# pop elements from the heap O(lg n)
min_x = heappop(x)
min_x = heappop(x)
min_x = heappop(x)

# push then pop an element (more efficient than separate)
min_x = heappushpop(x, 22)

# pop then push element
min_x = heapreplace(x, 22)