call-seq: Heap.new(optional_array) { |x, y| optional_comparison_fn } -> new_heap

If an optional array is passed, the entries in the array are inserted into the heap with equal key and value fields. Also, an optional block can be passed to define the function that maintains heap property. For example, a min-heap can be created with:

minheap = Heap.new { |x, y| (x <=> y) == -1 }
minheap.push(6)
minheap.push(10)
minheap.pop #=> 6

Thus, smaller elements will be parent nodes. The heap defaults to a min-heap if no block is given.

call-seq: change_key(key, new_key) -> [new_key, value] change_key(key, new_key) -> nil

Changes the key from one to another. Doing so must not violate the heap property or an exception will be raised. If the key is found, an array containing the new key and value pair is returned, otherwise nil is returned.

In the case of duplicate keys, an arbitrary key is changed. This will be investigated more in the future.

Complexity: amortized O(1)

minheap = MinHeap.new([1, 2])
minheap.change_key(2, 3) #=> raise error since we can't increase the value in a min-heap
minheap.change_key(2, 0) #=> [0, 2]
minheap.pop #=> 2
minheap.pop #=> 1

ameba:disable Metrics/CyclomaticComplexity

call-seq: clear -> nil

Removes all elements from the heap, destructively.

Complexity: O(1)

call-seq: delete(key) -> value delete(key) -> nil

Deletes the item with associated key and returns it. nil is returned if the key is not found. In the case of nodes with duplicate keys, an arbitrary one is deleted.

Complexity: amortized O(log n)

minheap = MinHeap.new([1, 2])
minheap.delete(1) #=> 1
minheap.size #=> 1

call-seq: empty? -> true or false

Returns true if the heap is empty, false otherwise.

call-seq: key?(key) -> true or false

Returns true if heap contains the key.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.key?(2) #=> true
minheap.key?(4) #=> false

call-seq: merge!(otherheap) -> merged_heap

Does a shallow merge of all the nodes in the other heap and clears the other heap

Complexity: O(1)

heap = MinHeap.new([5, 6, 7, 8])
otherheap = MinHeap.new([1, 2, 3, 4])
heap.merge!(otherheap)
heap.size #=> 8
heap.pop #=> 1

call-seq: next -> value next -> nil

Returns the value of the next item in heap order, but does not remove it.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.next #=> 1
minheap.size #=> 2

call-seq: next_key -> key next_key -> nil

Returns the key associated with the next item in heap order, but does not remove the value.

Complexity: O(1)

minheap = MinHeap.new
minheap.push(1, :a)
minheap.next_key #=> 1

call-seq: pop -> value pop -> nil

Returns the value of the next item in heap order and removes it from the heap.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.pop #=> 1
minheap.size #=> 1

call-seq: push(key, value) -> value push(value) -> value

Inserts an item with a given key into the heap. If only one parameter is given, the key is set to the value.

Complexity: O(1)

heap = MinHeap.new
heap.push(1, "Cat")
heap.push(2)
heap.pop #=> "Cat"
heap.pop #=> 2

call-seq: size -> int

Return the number of elements in the heap.