See the hacker news discussion:
https://news.ycombinator.com/item?id=7821552

Also, why not do a least common multiple while you're doing these things?

I remember this one for my data structures class!
http://en.wikipedia.org/wiki/2–3–4_tree

I noticed that a lot of the data structures(BST, HashTable, Set, etc) don't have iterators defined. Were they intentionally left out? If not then I wouldn't mind going through and adding them.

• Quicksort
• Merge sort
• Bubble sort
• BST
• Heap

This will allow doing custom sorting like in descending order and also perform it with different types of objects.

Everything passes and it fails on sonar-scanner, resulting in a negative overall result for PR.

Even for basic variable change PR #127 , sonar-scanner failed. There must be some issue with it.

This is the log from Travis-CI build.
The command "make" exited with 0.
0.11s$ sonar-scanner
sonar-scanner: command not found
The command "sonar-scanner" exited with 127.

var graph = graphFromEdges(false, [
[1, 2],
[1, 5]
]);

graph.edge("1","2")
1

graph.edge("1","constructor")
function Object() { [native code] }

hasOwnProperty can help here.

I got notifications for these, which are both 404 (page not found) when clicked.

https://github.com/felipernb/algorithms.js/releases/tag/0.1.0
https://github.com/felipernb/algorithms.js/releases/tag/0.2.0

I see
https://github.com/felipernb/algorithms.js/tree/v0.3.0
now but did not get a notification for it.

https://github.com/felipernb/algorithms.js/releases/tag/0.3.0
would also be 404.

The name "algorithms" doesn't seem to be taken yet on npm. You should consider publishing this module with that name. http://registry.npmjs.org/algorithms

I am finding some libraries about computational geometry, especially Bezier-curve related.

Including these algorithms will be helpful.

I've created a jsperf test to compare the performance of this library's implementation of quicksort agains the native Array.prototype.sort();

http://jsperf.com/algorithms-js-quicksort-vs-native-sort/4

Surprisingly, the quicksort in JS seems to be faster and I wonder if I'm doing something wrong, and maybe someone could help me verifying it.

Ping @eush77 @quietshu @joshuacurl 😁

A user should be able to load just some "module" of the library, like just the data_structures or just the sorting algorithms

Nice to see another person doing CS101 to keep themselves sharp. There are a couple of cute O(ln(n)) Fibonacci calculators to try:

• There's a very clever iterative solution in Abelson and Sussman's SICP (Ex. 1.19)
  https://github.com/sarabander/sicp-pdf/raw/master/sicp.pdf
• There's another crazy solution using Matrix exponentiation:
  https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
  You'll want an iterative O(ln(n)) matrix exponentiation algorithm, however, so you should check out SICP (Ex. 1.16)
• There's also the old trick of rounding powers of the golden ratio:
  https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
  Again, you can do this one iteratively in O(ln(n)), although a hand crafted exponentiation function will never outperform Math.pow on Chrome.
• Another approach is to use Binet's formula: fib(n) = (phi^n - phi^(-n)) / sqrt(5) ; you can use this iteratively without rounding by defining a custom class for Z[sqrt(5)]; see Integral Extensions for a discussion of this idea. Here's an implementation (in Haskell): https://github.com/jaycoskey/RealWorldBenchmarking/blob/master/Fibonacci/extension.hs
• Another neat way to solve this problem is to derive the closed form of the recurrence using the z transform. Here's a MathOverflow about it: https://math.stackexchange.com/questions/279868/causal-inverse-z-transform-of-fibonacci
  Again, an efficient, exact solution would require expressing the zeros of x^2 -x - 1 in Z[sqrt(5)] and defining iterative O(ln(n)) integer exponentiation for that ring. All of the ring extension solutions are less efficient than Abelson and Sussman's solution.

In order to have a 1.0 release we need:

1. Add self-balancing BSTs (red and black, avl, ...)
2. Add iterators (forEach) for all the data structures
3. Have a modular structure to allow someone to load just the sorting algorithms, for example, in a simple way

Adding the library to Bower would make it easier to use on front end projects than npm.

Bower is a package manager for the web. It offers a generic, unopinionated solution to the problem of front-end package management, while exposing the package dependency model via an API that can be consumed by a more opinionated build stack.

http://bower.io/#defining-a-package

Can't modern javascript compilers optimize this kind of instructions? I know this is kind of bikeshedding, but I think using shifts instead of multiplications only sacrifices readability of the code.

Thanks for providing this module.

I've used the PriorityQueue a bit and noticed something that looks like a bug to me. It seems like if the same element is inserted again after have being extracted once alrady, is not possible.

See this minimal example:

const PriorityQueue = require("algorithms/data_structures").PriorityQueue;

const q = new PriorityQueue();

// Inserting and extracting one time works as expected:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());
console.log(q.isEmpty());

// Inserting 'a' again does not work, queue will be empty and nothing to extract:
q.insert("a", 1);
console.log(q.isEmpty());
console.log(q.extract());

The outoupt of this is:

false
a
true
true
undefined

while the expected output is:

false
a
true
false
a

My system:

• node v19.2.0.
• macOS 13.0.1

I'm looking for a good way to find elements on a LinkedList (academic purpose), using a functional aproach.

The forEach iterate over all list applying a function, it's useful for some cases, discussed at #88.
When the scenario is only to search and return an element, the forEach can be used with a workaround:

var a;
list.forEach(function (e) {
        if (key === e) {
          a = e;
          return;
        };
    });

and it will perform over all elements. I want to stop at first match, something like

var a = list.find(function(e /*[, key [,comparator_func]]*/){...})  // return an element or null

The iterator pattern can be used, maybe just refactor some code...
What do you think about this?

We can do better, namely in O(log n).

Here's a simpler implementation of a Binary Heap; feel free to introduce a comparator into the constructor...

function PriorityQ(elems) {
// Implements a binary heap priority queue
    var q = [null];
    this.push = function (h) {
        var i, j;
        for (i = q.length; (j = (i / 2) | 0) && q[j] > h; q[i] = q[j], i = j);
        q[i] = h;
        return this;
    };
    this.pop = function () {
        var i, j, r, t;
        for (r = q[1]; q.length > 1 && r == q[1]; q[i] = t) {
            for (i = 1, t = q.pop(); (j = i * 2) < q.length;) {
                if (j < q.length && q[j] > q[j + 1]) j++;
                if (t <= q[j]) break;
                q[i] = q[i = j];
            }
        }
        return r;
    };
    if (Object.prototype.toString.call(elems) === '[object Array]')
        elems.forEach(this.push);
}

From this http://www.algorithmist.com/index.php/Bubble_sort

var bubbleSort = function(a) {
  var n = a.length,
    bound = n - 1;
  for (var i = 0; i < n - 2; i++) {
    var newbound = 0;
    for (var j = 0; j < bound; j++) {
      if (a[j] > a[j + 1]) {
        var tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
        newbound = j - 1;
      }
    }
    bound = newbound;
  }
  return a;
};

• Levenshtein

In its current form the binary search algorithm is not really useful, because in most cases it is not only the presence of a value that matters but also the position in the array.

I suggest that the binary search interface should mimic the standard Array#indexOf, in which case the algorithm could be considered as a more efficient alternative to indexOf for sorted arrays.

graph = new Graph(false)
graph.addEdge(1,2,-1)
graph.addEdge(2,3,-2)
graph.addEdge(3,4,0)
graph.addEdge(4,1,1)

SPFA(graph, "2")

The algorithm is going to infinite loop, because on every iteration we can improve shortest path.

Looks like algorithm should remember visited edges and break if it trying to visit some edge in the second time.

Hello guys!
Would be that interesting for you ?
The idea is: from usual parent -> children relations we build an hierarchied topology and calculate the x, y coords for the nodes to be shown on layout with specific width, height and make a general connections between nodes: connections to the same node from different nodes could be replaced with one common bus, etc.
I am going to implement it for the project in samsung.

For 1.0 it would be nice to have all algos and data structures documented properly on the wiki

see https://gist.github.com/Fil/8903368

may I add this topic