Algorithm Analysis

The Python code references the pseudocode from Cormen, T. H., & Leiserson, C. E. (2009). Introduction to algorithms, 3rd edition. https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf

The repository is made for better understanding of algorithm analysis (e.g. Binary Heap).

A one-dimensional array A viewed as a nearly complete binary tree T.
Each element of A corresponds to a node of T:
    A[1] is the root of T.
    For i >= 1, A[2i] is the left child of A[i], A[2i+1] is the right child of A[i].
    For i >= 2, A[floor(2i)] is the parent of A[i].

Basic functions:
    Parent(i)
        return floor(i/2)
    Left(i)
        return 2i
    Right(i)
        return 2i+1
    Max-Heap
        A[floor(i/2)] >= A[i]
    Min-Heap
        A[floor(i/2)] <= A[i]

Basic operations on max-heaps:
    Max-heapify
        maintain the max-heap property in O(log n) time.
    Build-max-heap
        build a max-heap from an unordered array in O(n) time.
    Heapsort
        sort an array in ascending order in O(n log n) time.
    Max-heap-increase-key
        increase the value of one element and then maintain the max-heap property in O(log n) time.
    Max-heap-insert
        insert a new element to a max-heap and then maintain the max-heap property in O(log n) time.
    Heap-Maximum
        return the maximum element of a max-heap
    Max-Heap-Delete
        delete the maximum element from a max-heap and then maintain the max-heap property in O(log n) time.