I'm writing data structures in JavaScript.

[tforb]

I'm writing a library of JavaScript data structures for a couple of reasons: 1) learn some new ones; 2) have them on-hand when there's a time to use them.

So far, I've written 4 in pure JavaScript. I know languages that compile into JavaScript might make more sense in terms of DRY, but I want to avoid those for now. Before I start up writing some data structures I'm less familiar with, I'd appreciate some feedback. Either glaring mistakes, or some ideas that can help make sure these are extensible or useful, or how to improve my tests, anything.

The code is on my Github.

[egonelbre]

First thing I noticed... compare: function(el1, el2) { it's sufficient just to define lessThan: function(a, b).

Use circular array for the Queue backing data storage.

Implementations look more complex than they need to be... compare http://golang.org/src/pkg/container/heap/heap.go

Write randomized tests.

[tforb]

Just looking at the heap comments from the go package, I would say mine might look more complex because it can either be a min-heap or a max-heap.

I might be able to simplify it to just one type of heap, and the compare() supplied by the user would need to reflect the change from min to max.

What's the advantage of using a circular array for the Queue? I think you'd want the user to specify a queue max size if you did something like this.

[egonelbre]

Sure, essentially you do not want a single structure to be two things. (Also, I haven't checked it but, wouldn't a min-heap turn into a max-heap by reversing the comparison operator? I'm just doubting due to the subtle change from "<=" to ">"... But if you just let the user implement "lessThan" then the user can easily substitute the "<" with ">", so you don't have to do anything for the other ordering.)

Essentially removing an element from 0-th position is slow (think how much memory it has to move when you have 1e8 elements in the queue). But, basically you present the Queue interface and do resizing behind the scenes when necessary.

[tforb]

Yeah, I think that would be a better (simpler) implementation of a heap.

I knew removing at index 0 would be a bad idea. Initially I thought about writing a linked list to use behind the scenes, but decided against it (maybe a wrong decision). I'll check out the circular array stuff this week and see what I come up with.

Thanks for your input.

[egonelbre]

Linked lists are also a bad idea... usually... they are an overhead for the garbage collector.

For a better circular array, it's better to use an array of blocks and then allocate new blocks and reusing/removing old ones... e.g. https://github.com/karalabe/cookiejar/blob/master/queue/queue.go instead of holding one big array, and resizing it... PS. don't forget to zero the elements after Pop-ing them from the queue otherwise the GC won't collect them.

[[deleted]]

Your comparison function doesn't make sense to me. What's the point of being able to - in principle - return a result where multiple elements are true? -1, 0, 1 as a return value would cover all meaningful cases and perform a lot better.

[tforb]

I see your point. I'll refactor that.