Class: DS::IndexedBinaryHeap

Inherits:
BinaryHeap show all
Defined in:
lib/ds/trees/indexed_binary_heap.rb

Overview

Indexed BinaryHeap

Instance Attribute Summary

Attributes inherited from BinaryHeap

#store

Instance Method Summary collapse

Methods inherited from BinaryHeap

#empty?, #heapify!, #insert, #length, max, min, #relation, #shift, #to_a, #top

Constructor Details

#initialize(*args, &block) ⇒ IndexedBinaryHeap

Create new IndexedHeap from args. Given block is used to set heap relation. Default heap relation is Max Heap.



7
8
9
10
11
12
13
14
15
 
# File 'lib/ds/trees/indexed_binary_heap.rb', line 7

def initialize(*args, &block)
  @relation = if block_given?
                block
              else
                -> (parent, child) { parent.key >= child.key }
              end
  @store = IndexedHeapStore.new(*args)
  heapify!
end

Instance Method Details

#change_priority(x, priority) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/ds/trees/indexed_binary_heap.rb', line 17

def change_priority(x, priority)
  node = get(x)
  old_priority = node.key
  return if old_priority == priority

  node.key = priority
  index = store.index(node.value)

  if higher?(priority, old_priority)
    swim(index)
  else
    sink(index)
  end
end

#get(x) ⇒ Object 



32
33
34
 
# File 'lib/ds/trees/indexed_binary_heap.rb', line 32

def get(x)
  store.get(x)
end

#include?(x) ⇒ Boolean

Returns:

  • (Boolean) 


36
37
38
 
# File 'lib/ds/trees/indexed_binary_heap.rb', line 36

def include?(x)
  get(x) ? true : false
end