Class: PairingHeap::PairingHeap
- Inherits:
-
Object
- Object
- PairingHeap::PairingHeap
- Defined in:
- lib/pairing_heap.rb
Overview
Pairing heap data structure implementation
Direct Known Subclasses
Instance Method Summary collapse
-
#any? ⇒ Boolean
Time Complexity: O(1).
-
#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)).
-
#delete(elem) ⇒ self
Removes element from the heap Time Complexity: O(N) Amortized Time Complexity: O(log(N)).
-
#each {|element| ... } ⇒ Enumerator<Object>
Returns enumerator of elements.
-
#each_with_priority {|element| ... } ⇒ Enumerator<Array(Object, Object)>
Returns enumerator of elements.
-
#empty? ⇒ Boolean
Time Complexity: O(1).
-
#get_priority(elem) ⇒ Object?
Returns priority of the provided element Time Complexity: O(1).
-
#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).
-
#include?(key) ⇒ Boolean
(also: #exists?)
Check if element is in the heap Time Complexity: O(1).
-
#initialize {|l_priority, r_priority| ... } ⇒ PairingHeap
constructor
A new instance of PairingHeap.
-
#peek ⇒ Object?
Returns the element at the top of the heap Time Complexity: O(1).
- #peek_priority ⇒ Object?
- #peek_with_priority ⇒ Array(Object, Object), Array(nil, nil)
-
#pop ⇒ Object?
(also: #dequeue)
Removes element from the top of the heap and returns it Time Complexity: O(N) Amortized time Complexity: O(log(N)).
- #pop_priority ⇒ Object?
- #pop_with_priority ⇒ Array(Object, Object), Array(nil, nil)
-
#push(elem, priority = elem) ⇒ self
(also: #enqueue, #offer)
Pushes element to the heap.
-
#size ⇒ Integer
(also: #length)
Time Complexity: O(1).
Constructor Details
#initialize {|l_priority, r_priority| ... } ⇒ PairingHeap
Returns a new instance of PairingHeap.
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)
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))
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))
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>
There are no order guarantees.
Returns enumerator of elements.
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)>
There are no order guarantees.
Returns enumerator of elements.
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)
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)
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)
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)
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)
106 107 108 |
# File 'lib/pairing_heap.rb', line 106 def peek @root&.elem end |
#peek_priority ⇒ Object?
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)
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))
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?
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)
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)
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)
136 137 138 |
# File 'lib/pairing_heap.rb', line 136 def size @nodes.size end |