/scala-data-structures

scala data structures and graph algorithms

Primary LanguageScala

Scala data structures and algorithms for graphs, trees and heaps.

QuickSort

  • swap elements in array
  • should partition array
  • should sort array with each strategy
  • should choose median
  • should sort dataset using first partitioning stategy
  • should sort dataset using last partitioning stategy
  • should sort dataset using median partitioning stategy
  • should sort dataset using random partitioning stategy

Heap

  • should calculate left, right and parent element index
  • should insert element while maintaining min-heap property
  • should insert element while maintaining max-heap property
  • should extract head while maintaining heap property
  • should remove element while maintaining heap property
  • should compute sum of moving medians

Graph

  • should have nodes and edges
  • should have hardCopyReversed graph
  • should search graph with dfs
  • should find strongly connected components
  • should read adjacent list graph from file
  • should read adjacent-weight list graph from file
  • should breath-first search the graph - sccGraph
  • should depth-first search the graph - dijkstraGraph
  • should depth-first search the graph - sccGraph
  • should find cycles - graph2
  • should find cycles - graph3
  • should check cycles
  • should sort topologically - graph3
  • should sort topologically - graph4
  • should compute shortest path - graph3
  • should compute shortest path - dijkstraData
  • should compute all shortest paths - graph3
  • should compute all shortest paths - dijkstraData
  • should merge nodes
  • should find min cut count
  • should find strongly connected components - scc