Skip to main content

Python

💬Work in Progress

Work in Progress. Check back later.

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.

Pasted image 20220904230841.png

  • 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(Nlogk)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(Nlogk)O(N \log k)
OperationRuntime
Find min/maxO(1)O(1)
SearchO(n)O(n)
InsertO(logn)O(\log n)
RemoveO(logn)O(\log n)
Heapify ArrayO(n)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)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)]