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


70
71
72
73
74
# File 'lib/pairing_heap.rb', line 70

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

Instance Method Details

#any?Boolean

Time Complexity: O(1)

Returns:

  • (Boolean)

110
111
112
# File 'lib/pairing_heap.rb', line 110

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


154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
# File 'lib/pairing_heap.rb', line 154

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]

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

#delete(elem) ⇒ PairingHeap

Removes element from the heap

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

Returns:

Raises:

  • (ArgumentError)

    if the element heap is not in heap


176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
# File 'lib/pairing_heap.rb', line 176

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
    node.remove_from_parents_list!
    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)

104
105
106
# File 'lib/pairing_heap.rb', line 104

def empty?
  @root.nil?
end

#peekObject

Returns the element at the top of the heap

Time Complexity: O(1)

94
95
96
# File 'lib/pairing_heap.rb', line 94

def peek
  @root&.elem
end

#peek_priorityObject


98
99
100
# File 'lib/pairing_heap.rb', line 98

def peek_priority
  [@root&.elem, @root&.priority]
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


126
127
128
129
130
131
132
133
134
135
136
137
138
# File 'lib/pairing_heap.rb', line 126

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

#pop_priorityObject


141
142
143
144
145
# File 'lib/pairing_heap.rb', line 141

def pop_priority
  node = @root
  pop
  [node.elem, node.priority]
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


82
83
84
85
86
87
88
89
# File 'lib/pairing_heap.rb', line 82

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)

116
117
118
# File 'lib/pairing_heap.rb', line 116

def size
  @nodes.size
end