Skip to content

Latest commit

 

History

History
39 lines (34 loc) · 1.84 KB

README.mdown

File metadata and controls

39 lines (34 loc) · 1.84 KB
Raw

Algorithms and Data Structures

A collection of algorithms and data structures implementations

Overview

  1. Linkedlist (C)
    • Supported Ops : Push, Pop, Delete, Length, Disply, GetNth, Push at end, Insert at nth.
  2. Tree (C)
    • Supported Ops : Build, Random insert, Display Rree, Count Red Children.
  3. Range Minimum Query
    • Supported Ops: Query, Update, Print.
    • Algos : Preprocess, Query
    • LookupTable : O(n^2), O(1)
    • SqrtPart : O(n), O(sqrt(n))
    • SparseTable : O(nlogn), O(1)
  4. Binary Heap
    • Supported Ops: Heapify, FindXtrma, ExtractXtrma, Insert, Delete, IncreaseKey, DeacreaseKey,
  5. Tree atop an Array
    • Supported Ops: Build, Sum(i,j), Max/Min(i,j), Update(k,j).
  6. Disjoint Set Data Structure
    • Supported Ops: FindSet, UnionSet, PrintGraph (in GraphViz format).
    • Heavily influenced on Pedro Felzenswalb's Disjoint Set Implementation.
  7. Interval Trees.
    • Supported Operations :
    • Supports dynamic operations, with amortized rebalancing.
DS Build Space Query Update
Linkedlist O(n)
Tree O(logn) O(logn)
Binary Heap O(n)
Disj Set O(alpha(n))
RMQ O(n^2/O(n) O(1)/O(sqrt(n) 'X'
TreeAtopArray O(nlogn) O(nlogn) O(logn) O(logn)

Note: The above comlexity analysis is only a rough guide to the complexity of the implemented method, but they hold only for the abstract model they are part of, and might not have the exact gaurantees on real world computers. Further the Disjoint set data structure is implemented with both path compression and union by rank, though it might not exactly have the gaurantees stated above.