Heap is broken with objects

[fbernier]

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

[dirkholzapfel]

any updates on this issue?

[fbernier]

@dirkholzapfel I ended up using https://github.com/rubyworks/pqueue instead

[shiduanguang]

If you let the elements not same, this err wont be raised.

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

while val = min_heap.pop do
  p val
end

But if you need elements to be same, just replace Heap with MaxHeap or MinHeap.

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

while val = min_heap.pop do
  p val
end

[shiduanguang]

This Heap is slower very much than Ruby's built in Array sorting. I'm using Ruby 2.2.4.

[TedTran2019]

This is still the case. If you're here because Leetcode uses this as the algorithm library for Ruby, I'd suggest just directly copy pasting florian's rb_heap into the editor instead

class Heap
  def initialize(compare_symbol = :<, storage = [], &compare_fn)
    @heap = storage
    @size = 0
    initialize_compare(compare_symbol, &compare_fn)
  end

  attr_reader :size

  def empty?
    size == 0
  end

  def peak
    @heap[0]
  end

  def pop
    result = peak

    if size > 1
      @size -= 1
      @heap[0] = @heap[@size]
      rebalance_down(0)
    else
      @size = 0
    end

    @heap[@size] = nil

    result
  end

  def add(element)
    @heap[@size] = element
    @size += 1
    rebalance_up(size - 1)
    self
  end

  alias << add

  def replace(element)
    @heap[0] = element
    rebalance_down(0)
  end

  def offer(element)
    if compare(peak, element)
      result = peak
      replace(element)
      result
    else
      element
    end
  end

  def clear
    @heap = []
    @size = 0
  end

  def to_a
    @heap.reject { |element| element.nil? }
  end

  private

  def initialize_compare(symbol, &fn)
    @compare = if block_given?
                 fn
               elsif symbol == :< or symbol.nil?
                 ->(a, b) { a < b }
               elsif symbol == :>
                 ->(a, b) { a > b }
               else
                 raise ArgumentError.new('The comparison symbol needs to be either :> or :<')
               end
  end

  def compare(a, b)
    @compare.call(a, b)
  end

  def rebalance_up(i)
    parent_i = parent(i)

    return unless has_parent(i) and compare(@heap[i], @heap[parent_i])

    @heap[i], @heap[parent_i] = @heap[parent_i], @heap[i]
    rebalance_up(parent_i)
  end

  def rebalance_down(i)
    left_i = left(i)
    right_i = right(i)

    if has_left(i) and compare(@heap[left_i], @heap[i]) and (!has_right(i) or compare(@heap[left_i], @heap[right_i]))
      @heap[i], @heap[left_i] = @heap[left_i], @heap[i]
      rebalance_down(left_i)
    elsif has_right(i) and compare(@heap[right_i], @heap[i])
      @heap[i], @heap[right_i] = @heap[right_i], @heap[i]
      rebalance_down(right_i)
    end
  end

  def has_parent(i)
    i >= 1
  end

  def parent(i)
    ((i - 1) / 2).floor
  end

  def has_left(i)
    left(i) < size
  end

  def left(i)
    i * 2 + 1
  end

  def has_right(i)
    right(i) < size
  end

  def right(i)
    i * 2 + 2
  end
end

[giorgenes]

+1 for this.
I've spent 2 days debugging why my code didn't work, until I decided to add my own heap implementation. Turns out it's broken for objects. (I implemented the <=> method).