Heap min order incorrect when using custom comparator

[sheend]

With this ListNode definition and custom Heap

class ListNode
    attr_accessor :val, :next
    def initialize(val = 0, _next = nil)
        @val = val
        @next = _next
    end
end

pq = MinHeap.new do |a, b|
    result = a.val <=> b.val
    result == 0 ? a.object_id <=> b.object_id : result
end
pq.push(ListNode.new(1))
pq.push(ListNode.new(1))
pq.push(ListNode.new(2))
pq.push(ListNode.new(4))
while !pq.empty? do
    p pq.pop
end

gives you 4 before 2

#<ListNode:0x00007f2fd6bf4a70 @val=1, @next=nil>
#<ListNode:0x00007f2fd6bf4818 @val=1, @next=nil>
#<ListNode:0x00007f2fd6bf44a8 @val=4, @next=nil>
#<ListNode:0x00007f2fd6bf4548 @val=2, @next=nil>

but if you do it yourself in the ListNode itself:

class ListNode
    attr_accessor :val, :next
    def initialize(val = 0, _next = nil)
        @val = val
        @next = _next
    end

    def <=>(other)
        return nil if !other.is_a?(ListNode)
        result = val <=> other.val
        result == 0 ? object_id <=> other.object_id : result
    end
end

pq = MinHeap.new
pq.push(ListNode.new(1))
pq.push(ListNode.new(1))
pq.push(ListNode.new(2))
pq.push(ListNode.new(4))
while !pq.empty? do
    p pq.pop
end

you get the correct result as expected:

#<ListNode:0x00007fb49794eff0 @val=1, @next=nil>
#<ListNode:0x00007fb49794ebb8 @val=1, @next=nil>
#<ListNode:0x00007fb49794e410 @val=2, @next=nil>
#<ListNode:0x00007fb49794e370 @val=4, @next=nil>

[yugonline]

Have you tried passing the bloc to Heap.new instead of MinHeap? It doesn’t seem like MinHeap accepts a bloc as it’s just a convenience class on top of Heap.

algorithms/lib/containers/heap.rb

Line 455 in feaa5d5

class Containers::MinHeap < Containers::Heap

[sheend]

I believe this was fixed in #60

[yugonline]

Oh okay glad your problem was resolved. But my thought process wasn’t on the latest changes but on you using MinHeap in this code block. If it’s just for example purpose then that makes sense however I’m not sure if MinHeap accepts a bloc.

pq = MinHeap.new do |a, b| result = a.val <=> b.val result == 0 ? a.object_id <=> b.object_id : result end