Python

tip

Special thanks to Ishu Agrawal

Heap

Heaps are complete binary trees where the value of each node must be no greater than (or less than) the value of its child nodes.

• Python only supports Min Heaps
• import heapq
• heapq.heapify(arr)
• heapq.heappop(arr)
• heapq.heappush(arr, x)
• heapq.nsmallest(k, arr, key=func) returns a list with the k smallest elements in the iterable arr based on a comparator function func
  • Runtime: $O(N \log k)$
• heapq.nlargest(k, arr, key=func)returns a list with the k largest elements in the iterable arr based on a comparator function func
  • Runtime: $O(N \log k)$

Operation	Runtime
Find min/max	$O(1)$
Search	$O(n)$
Insert	$O(\log n)$
Remove	$O(\log n)$
Heapify Array	$O(n)$

List Offsetting

You can offset with Python's enumerate function with list splitting.

enumerate(nums[offset::])

Dictionary

• Python Dictionary is a hash map.
• Lookup time: $O(n)$ worst when there are many collisions.

Alphanumeric Testing

• c.isalnum()

Making 2d Arrays

• using visited = [[False] * len(image[0])] * len(image) will not work
  • the rows will share the same memory and change in one will reflect on the others
• use arr = [[0 for i in range(cols)] for j in range(rows)]