PYthon Algorithms Library (pyal)

Unlike the STL in C++ which provides misceneous data structures, Python does not have some important structures, like linked list, tree map. This library aims to provide a python counterpart of C++ STL.

1. Install

python3 -m pip install Python-Algorithm-pyal psutil pytz

2. Examples github

Balanced search tree based map, TreeMap

import pyal

def main():
  tree_map = pyal.TreeMap()
  data = [(0, "a"), (1, "b"), (2, "c"), (3, "d"), (4, "e"), (5, "f")]
  for key, value in data:
    tree_map[key] = value

  key = -1
  value = tree_map.get(key)
  if value is None:
    print(f"key={key} does not exist")

  key = 0
  print(f"key={key}, value={tree_map[key]}")

  key = 1
  node = tree_map.lower_bound(key)
  print(f"lower_bound({key=}): {node.get()=}")

  node = tree_map.upper_bound(key)
  print(f"upper_bound({key=}): {node.get()=}")

  print(f"min key: {tree_map.key_list_begin().get()}")
  print(f"max key: {tree_map.key_list_end().prev().get()}")

Output

key=-1 does not exist
key=0, value=a
lower_bound(key=1): node.get()=1
upper_bound(key=1): node.get()=2
min key: 0
max key: 5

3. Popular data structures and algorithms.

Please check github for all examples.

• Tree

  • TreeMap example
    • Balanced binary search tree.
    • insert & delete: O(log N)
    • get: O(1)
  • DynamicHeap example
    • update & deletion: O(log N)
  • MinHeap, MaxHeap example
  • DisjointSet example

• List

  • LinkedList example
  • Queue example
  • Dequeue example
  • Stack example
  • LRUCache example
    • get & set: O(1)
  • LFUCache example
    • get & set: O(1)

• String

  • search_KMP
  • search_multipatterns
  • todo

• Graph

  • Graph
  • Dijkstra
  • topological_traversal

• Common useful functions

  • binary_search
    • General binary search, binary_search(sorted_data, from, to, user_func), where user_func(x) defines the data as [False, ..., False, True, ..., True], this function returns the first position of 'True'.
    • Many practical problems can be converted to this form, like binary_find, lower_bound, upper_bound, peak position in a rotated sorted array and etc.
  • is_none_or_empty
  • histogram_ascii
  • is_sorted
  • unique
  • cmp
  • split_data_by_func
  • eq
  • discrete_sample
  • group_by_key_fun
  • top_n
  • clamp
  • argmax
  • argmin
  • make_list
  • swap
  • rotate
  • copy_to
  • kth_smallest_element
  • lower_bound
  • upper_bound
  • reverse_in_place
  • sort_in_place
  • find_first_if
  • find_last_if
  • next_permutation
  • prev_permutation
  • factorial
  • combinatorial_number
  • permutation_number
  • combinations_with_duplicate
  • longest_common_substr
  • top_k_similar