make-github-pseudonymous-again / js-data-structures Goto Github PK

View Code? Open in Web Editor NEW

57.0 6.0 3.0 2.08 MB

:herb: Data structures for JavaScript

License: GNU Affero General Public License v3.0

javascript data-structure data-structures persitent immutable functional dict lifo fifo graphs

js-data-structures's People

Contributors

Stargazers

Watchers

Forkers

jingchun01 cubuanic-js

js-data-structures's Issues

explore other implementations of binomial heaps

use a backreference to keep track of nodes instead of swapping childrens
- faster because we only need to swap values and backreferences
- additional memory used
implementation only supporting push pop and merge

Fenwick tree

https://en.wikipedia.org/wiki/Fenwick_tree

js-fliplist

List with O(1) merge/reverse/insert/delete and dynamic pointers.
Merge can invalidate one of the list's iterators. Can be overcomed using union-find.

explore other implementations of d-ary heaps

see http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps

augment lazy binomial heap

add the update, delete, decreasekey and increasekey operations

Bottom-up Heapsort siftdown

http://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort

Fusion Trees

https://en.wikipedia.org/wiki/Fusion_tree

Order statistic tree

https://en.wikipedia.org/wiki/Order_statistic_tree
(A persistent implementation can be built on top of fingertrees, see IndOrdSeq in https://github.com/aureooms/js-persistent)

implement radix tree

see https://en.wikipedia.org/wiki/Radix_tree

js-heap-spec

create documentation repository for heap interfaces

Chan's algorithm [SoCG16]
encode data as a polynomial
A(x) = (sum f(x_i)^p)^(1/p)
approx f. = n^(1/p)
C(x) = (sum i f(x_i)^p)^(1/p)
p = 1/e log n
C(x)/A(x)
insert / delete is just addition subtraction of a value
use different buckets to avoid issues with points that are too close

fork js-dll

O(n) makeheap

// >= 0 is necessary when arity = 1 and n = 0
for ( k = ( n + arity - 2 ) / arity | 0 ; k-- >= 0 ; ) {
    siftdown( arity , compare , swap , a , 0 , n , k ) ;
}

Top Tree

https://en.wikipedia.org/wiki/Top_tree

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG), Vol. 1 (2005), 243–264, doi:10.1145/1103963.1103966
Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM, Vol. 48 Issue 4(July 2001), 723–760, doi:10.1145/502090.502095
Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp. 308–423.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.
Tree Compression with Top Trees. BILLE, GOERTZ, LANDAU, WEIMANN 2013 arXiv:1304.5702 [cs.DS]