Class: PairingHeap::PairingHeap

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

Overview

Pairing heap data structure implementation

See Also:

Instance Method Summary collapse

Constructor Details

#initialize {|l_priority, r_priority| ... } ⇒ PairingHeap

Returns a new instance of PairingHeap.

Yields:

  • (l_priority, r_priority) —

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

Yield Returns:

  • (boolean) —

    if ‘l_priority` is more prioritary than `r_priority`, or the priorities are equal



75
76
77
78
79
 
# File 'lib/pairing_heap.rb', line 75

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

Instance Method Details

#any? ⇒ Boolean

Time Complexity: O(1)

Returns:

  • (Boolean) 


130
131
132
 
# File 'lib/pairing_heap.rb', line 130

def any?
  !@root.nil?
end

#change_priority(elem, priority) ⇒ self

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:

  • (self)

Raises:

  • (ArgumentError) —

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



186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/pairing_heap.rb', line 186

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 self if node.parent.nil?
  return self if @order[node.parent.priority, node.priority]

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

#delete(elem) ⇒ self

Removes element from the heap

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

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    if the element is not in the heap



208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/pairing_heap.rb', line 208

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)
    if @root
      @root.parent = nil
      @root.prev_sibling = nil
      @root.next_sibling = nil
    end
  else
    node.remove_from_parents_list!
    new_heap = merge_pairs(node.subheaps)
    if new_heap
      @root = meld(new_heap, @root)
      @root.parent = nil
      @root.prev_sibling = nil
      @root.next_sibling = nil
    end
  end
  self
end

#each {|element| ... } ⇒ Enumerator<Object>

Note:

There are no order guarantees.

Returns enumerator of elements.

Yield Parameters:

  • element (Object) —

    Element in the heap

Returns:

  • (Enumerator<Object>) 


265
266
267
268
 
# File 'lib/pairing_heap.rb', line 265

def each
  return to_enum(__method__) { size } unless block_given?
  @nodes.each_value { |node| yield node.elem }
end

#each_with_priority {|element| ... } ⇒ Enumerator<Array(Object, Object)>

Note:

There are no order guarantees.

Returns enumerator of elements.

Yield Parameters:

  • element (Array(Object, Object)) —

    Element in the heap with its priority

Returns:

  • (Enumerator<Array(Object, Object)>) —

    if no block given



274
275
276
277
 
# File 'lib/pairing_heap.rb', line 274

def each_with_priority
  return to_enum(__method__) { size } unless block_given?
  @nodes.each_value { |node| yield [node.elem, node.priority] }
end

#empty? ⇒ Boolean

Time Complexity: O(1)

Returns:

  • (Boolean) 


124
125
126
 
# File 'lib/pairing_heap.rb', line 124

def empty?
  @root.nil?
end

#get_priority(elem) ⇒ Object?

Returns priority of the provided element

Time Complexity: O(1)

Returns:

  • (Object)
  • (nil) —

    If element does not exist



245
246
247
248
 
# File 'lib/pairing_heap.rb', line 245

def get_priority(elem)
  node = @nodes[elem]
  node&.priority
end

#get_priority_if_exists(elem) ⇒ Array(false, nil), Array(true, Object)

Returns a pair where first element is success flag, and second element is priority

Time Complexity: O(1)

Returns:

  • (Array(false, nil)) —

    if the element is not in heap

  • (Array(true, Object)) —

    if the element is in heap; second element of returned tuple is the priority



255
256
257
258
259
 
# File 'lib/pairing_heap.rb', line 255

def get_priority_if_exists(elem)
  node = @nodes[elem]
  return [false, nil] if node.nil?
  [true, node.priority]
end

#include?(key) ⇒ Boolean Also known as: exists?

Check if element is in the heap

Time Complexity: O(1)

Returns:

  • (Boolean) 


236
237
238
 
# File 'lib/pairing_heap.rb', line 236

def include?(key)
  @nodes.key?(key)
end

#peek ⇒ Object?

Returns the element at the top of the heap

Time Complexity: O(1)

Returns:

  • (Object)
  • (nil) —

    if the heap is empty



106
107
108
 
# File 'lib/pairing_heap.rb', line 106

def peek
  @root&.elem
end

#peek_priority ⇒ Object?

Returns:

  • (Object)
  • (nil) —

    if the heap is empty



112
113
114
 
# File 'lib/pairing_heap.rb', line 112

def peek_priority
  @root&.priority
end

#peek_with_priority ⇒ Array(Object, Object), Array(nil, nil)

Returns:

  • (Array(Object, Object))
  • (Array(nil, nil)) —

    if the heap is empty



118
119
120
 
# File 'lib/pairing_heap.rb', line 118

def peek_with_priority
  [@root&.elem, @root&.priority]
end

#pop ⇒ Object? Also known as: dequeue

Removes element from the top of the heap and returns it

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

Returns:

  • (Object) —

    The top element

  • (nil) —

    If the heap is empty



146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/pairing_heap.rb', line 146

def pop
  return nil 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_priority ⇒ Object?

Returns:

  • (Object)
  • (nil) —

    if the heap is empty

See Also:



164
165
166
167
168
 
# File 'lib/pairing_heap.rb', line 164

def pop_priority
  node = @root
  pop
  node&.priority
end

#pop_with_priority ⇒ Array(Object, Object), Array(nil, nil)

Returns:

  • (Array(Object, Object))
  • (Array(nil, nil)) —

    If the heap is empty

See Also:



173
174
175
176
177
 
# File 'lib/pairing_heap.rb', line 173

def pop_with_priority
  node = @root
  pop
  [node&.elem, node&.priority]
end

#push(elem, priority = elem) ⇒ self Also known as: enqueue, offer

Pushes element to the heap.

Time Complexity: O(1)

Parameters:

  • elem —

    Element to be pushed

  • priority (defaults to: elem) —

    Priority of the element

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    if the element is already in the heap



87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/pairing_heap.rb', line 87

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

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

#size ⇒ Integer Also known as: length

Time Complexity: O(1)

Returns:

  • (Integer) 


136
137
138
 
# File 'lib/pairing_heap.rb', line 136

def size
  @nodes.size
end