Class: PairingHeap::PairingHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/pairing_heap.rb

Overview

Pairing heap data structure implementation

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ PairingHeap

Returns a new instance of PairingHeap.

Parameters:

  • &block

    Optional heap property priority comparator. `<:=.to_proc` by default


21
22
23
24
25
# File 'lib/pairing_heap.rb', line 21

def initialize(&block)
  @root = nil
  @nodes = {}
  @order = block || :<=.to_proc
end

Instance Method Details

#any?Boolean

Time Complexity: O(1)

Returns:

  • (Boolean)

57
58
59
# File 'lib/pairing_heap.rb', line 57

def any?
  !@root.nil?
end

#change_priority(elem, priority) ⇒ PairingHeap

Changes a priority of element to a more prioritary one

Time Complexity: O(1)
Amortized Time Complexity: o(log(N))

Parameters:

  • elem

    Element

  • priority

    New priority

Returns:

Raises:

  • (ArgumentError)

    if the element heap is not in heap or the new priority is less prioritary


95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# File 'lib/pairing_heap.rb', line 95

def change_priority(elem, priority)
  node = @nodes[elem]
  raise ArgumentError, "Provided element is not in heap" if node.nil?
  unless @order[priority, node.priority]
    raise ArgumentError, "Priority cannot be changed to a less prioritary value."
  end

  node.priority = priority
  return if node.parent.nil?
  return if @order[node.parent.priority, node.priority]

  remove_from_parents_list(node)
  @root = meld(node, @root)
  @root.parent = nil
  self
end

#delete(elem) ⇒ PairingHeap

Removes element from the top of the heap

Time Complexity: O(N)
Amortized Time Complexity: O(log(N))

Returns:

Raises:

  • (ArgumentError)

    if the element heap is not in heap


117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# File 'lib/pairing_heap.rb', line 117

def delete(elem)
  node = @nodes[elem]
  raise ArgumentError, "Provided element is not in heap" if node.nil?

  @nodes.delete(elem)
  if node.parent.nil?
    @root = merge_pairs(node.subheaps)
  else
    remove_from_parents_list(node)
    new_heap = merge_pairs(node.subheaps)
    if new_heap
      new_heap.prev_sibling = nil
      new_heap.next_sibling = nil
    end
    @root = meld(new_heap, @root)
  end
  @root&.parent = nil
  self
end

#empty?Boolean

Time Complexity: O(1)

Returns:

  • (Boolean)

51
52
53
# File 'lib/pairing_heap.rb', line 51

def empty?
  @root.nil?
end

#peekObject

Returns the element at the top of the heap

Time Complexity: O(1)

45
46
47
# File 'lib/pairing_heap.rb', line 45

def peek
  @root&.elem
end

#popPairingHeap Also known as: dequeue

Removes element from the top of the heap

Time Complexity: O(N)
Amortized time Complexity: O(log(N))

Returns:

Raises:

  • (ArgumEntError)

    if the heap is empty


73
74
75
76
77
78
79
80
81
82
83
84
85
# File 'lib/pairing_heap.rb', line 73

def pop
  raise ArgumentError, "Cannot remove from an empty heap" if @root.nil?

  elem = @root.elem
  @nodes.delete(elem)
  @root = merge_pairs(@root.subheaps)
  if @root
    @root.parent = nil
    @root.next_sibling = nil
    @root.prev_sibling = nil
  end
  elem
end

#push(elem, priority) ⇒ PairingHeap Also known as: enqueue

Pushes element to the heap.

Time Complexity: O(1)

Parameters:

  • elem

    Element to be pushed

  • priority

    Priority of the element

Returns:

Raises:

  • (ArgumentError)

    if the element is already in the heap


33
34
35
36
37
38
39
40
# File 'lib/pairing_heap.rb', line 33

def push(elem, priority)
  raise ArgumentError, "Element already in the heap" if @nodes.key?(elem)

  node = Node.new(elem, priority, nil, nil, nil, nil)
  @nodes[elem] = node
  @root = meld(@root, node)
  self
end

#sizeInteger Also known as: length

Time Complexity: O(1)

Returns:

  • (Integer)

63
64
65
# File 'lib/pairing_heap.rb', line 63

def size
  @nodes.size
end