codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
202 stars 270 forks source link

Added Sparse table data structure for RMQ #414

Closed pratikgl closed 3 years ago

pratikgl commented 3 years ago

[WIP] I have added sparse table for solving Range Minimum Query

References to other Issues or PRs or Relevant literature

I am trying to replicate this idea which I had implemented a while ago in C++. https://github.com/pratikgl/Data-Structures-and-Algorithms/blob/master/RMQ/sparse_table.cpp

The sparse table implementation for RMQ will take O(n*log(n))) time for preprocessing and O(1) time for each query

More details could be find here:

  1. https://cp-algorithms.com/data_structures/sparse-table.html

    Brief description of what is fixed or changed

Other comments

codecov[bot] commented 3 years ago

Codecov Report

Merging #414 (2c4510d) into master (c726bf2) will decrease coverage by 0.038%. The diff coverage is 97.391%.

@@              Coverage Diff              @@
##            master      #414       +/-   ##
=============================================
- Coverage   98.611%   98.573%   -0.039%     
=============================================
  Files           27        29        +2     
  Lines         3530      3645      +115     
=============================================
+ Hits          3481      3593      +112     
- Misses          49        52        +3     
Impacted Files Coverage Δ
pydatastructs/utils/__init__.py 100.000% <ø> (ø)
...tructs/miscellaneous_data_structures/algorithms.py 95.833% <95.833%> (ø)
...ucts/miscellaneous_data_structures/sparse_table.py 97.142% <97.142%> (ø)
...astructs/miscellaneous_data_structures/__init__.py 100.000% <100.000%> (ø)
pydatastructs/utils/misc_util.py 99.043% <100.000%> (+0.148%) :arrow_up:

Impacted file tree graph

czgdp1807 commented 3 years ago

The PR syntactically is correct. There are some memory issues with implementation. We can fix that though. RangeMinimumQuery is good. Just add a class for array data structure as well.

czgdp1807 commented 3 years ago

Thanks @pratikgl