Works when the heap length is < 10 but fails with 10+

min_heap = ::Containers::Heap.new(10.times.map{Object.new}){|x, y| (x <=> y) == -1}

while val = min_heap.pop do
  p val
end

RuntimeError: Couldn't delete node from stored nodes hash

There are several releases on rubygems.org without corresponding git tags. It'd be helpful to have those for reproducibility.

One of the key advantages of heap sort is it can be an in place algorithm (https://en.wikipedia.org/wiki/In-place_algorithm); however, your implementation does not do an in place implementation:

https://github.com/kanwei/algorithms/blob/master/lib/algorithms/sort.rb#L85-L90

Instead, you are popping the values off the heap and putting them in a new array (when they could be kept in that array but moved to the end). Instead of calculating the size of the array in the heap, you could keep an index for the end of the heap within the array, and thus move the sorted values that have been popped off to the end of the actual array and decrement the heap's index.

At a minimum, the array here could be instantiated with the known size of the container. That prevents the array from being resized repeatedly (Ruby resizes an array when it hits 3, 20, 37, 56, 85, ... sizes, see here: https://github.com/ruby/ruby/blob/ruby_2_0_0/array.c#L183)

I was attempting to benchmark Conaitiner::RBTreeMap against ::RBTree and am able to consistently get a segmentation fault that appears to be triggered by Container::RBTreeMap when used within the context of Benchmark.

I the simplest use case that consistently segfaults for me here https://gist.github.com/copiousfreetime/46ce78f08885b24bc8dd.

It always segfaults during a write operation.

Only 1 line is different:

OK: https://leetcode.com/submissions/detail/1075862918/

@t.delete p if @t[p]

Not OK: https://leetcode.com/submissions/detail/1075860617/

@t.delete p

There is a note at the top of the KD Tree implementation that states that the current version contains bugs. Is this simply an outdated comment or is there in fact bugs within the implementation?

Kind Regards,

I installed the 0.2 gem (via gem install), copy paste the tree test in my editor (removed first line at the top and put the "require 'rubygems'" at the top),
Just launched it and get a segfault ... everything goes well if I dont populate the sbtree and the rbtree by commenting that lines :

      rbtree { random_array.each_with_index  { |x,index| rbtree[index] = x } }  
      splaytree { random_array.each_with_index  { |x,index| splaytree[index] = x } }  

It would be great if the binary search method return the index of the object in the array instead of the object itself. The index gives you more information (where it is instead of just whether or not it exists) and it's free-- you already have it when returning.

Hi there.

While using the library (specially the splay tree) as backend to a project, I did a stress test and found my app segfaulting under some strange and very specific conditions (300,000 items added to the tree in one loop followed by another loop of 300,000 items, no problem. 350,000 items added in one loop = segfault).

This is recreatable by loading your benchmarks for the treemaps and changing the array size to 261_123 (or any value above 261,122).

It's a pretty common problem (and we have this problem :)) where you want a priority queue that "loses" items of lesser priority (has a max size). What do you think of extending heap?

Not sure if this is a good name for it. We do a lot of fetching an array from the top of the heap (priority queue).

def top(max)
  results = []
  while results.size < max and size > 0 do 
    results << pop 
  end
  results
end

If you think it's a good idea, I'll make a proper pull request with a UT.

Quicksort should first randomly shuffle the container. If it doesn't and the array is already sorted, then it will actually be O(n^2), which is the worst case. By shuffling, it results in a probabilistic guarantee of О(n log n).

https://github.com/kanwei/algorithms/blob/master/lib/algorithms/sort.rb#L180

See: http://stackoverflow.com/questions/27645471/how-does-random-shuffling-in-quick-sort-helps-in-increasing-the-efficiency-of-th

Please refer to this stackoverflow question: http://stackoverflow.com/questions/13978484/kanwei-minheap-slow-ruby

I had to look around a bit to locate the repository because I ended up at the homepage first.

I want to contribute to this repository but, I am not able to understand the folder structure.

Building native extensions. This could take a while...
/custom/jruby/lib/ruby/1.8/mkmf.rb:7: JRuby does not support native extensions. Check wiki.jruby.org for alternatives. (NotImplementedError)
from /custom/jruby/lib/ruby/1.8/mkmf.rb:1:in `require'
from extconf.rb:1
ERROR: Error installing algorithms:
ERROR: Failed to build gem native extension.