Class: BinaryHeap

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

Overview

An implementation of standard binary heap data structure. Internally, it uses an array as data store and a mutex for thread synchronization (insert and eject operations)

Defined Under Namespace

Classes: Error, HeapError, ParameterError

Instance Method Summary collapse

Constructor Details

#initialize(data = nil, &block) ⇒ BinaryHeap

The constructor

Examples:

A default max heap

bh = BinaryHeap.new

A min heap

bh = BinaryHeap.new{|parent, child| child <=> parent}

A max heap using self-defined comparator

bh = BinaryHeap.new{|parent, child| parent.bigger_or_equal_than(child)}

Parameters:

  • data (Array) (defaults to: nil)

    the existent Array data on which the binary heap will be built

  • block (Block)

    the comparator block, see examples.

    default comparator is lambda {|parent, child| parent <=> child} which makes it a max binary heap.

Raises:


32
33
34
35
36
37
38
# File 'lib/binaryheap.rb', line 32

def initialize(data=nil, &block)
  @cmp = block || lambda{|parent, child| parent <=> child }
  @mutex = Mutex.new

  raise ParameterError.new("type of data must be Array or its subclass") unless data.nil? || data.is_a?(Array)
  @ary = data.nil? ? [] : build_from(data)
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

#method_missing(name, *args, &blcok) ⇒ Object

Forward methods to underlying Array instance


113
114
115
# File 'lib/binaryheap.rb', line 113

def method_missing(name, *args, &blcok)
  @ary.send(name, *args, &blcok)
end

Instance Method Details

#adjust(direction = :top_down) ⇒ BinaryHeap

Note:

this method should be used carefully since it is not thread-safe, please check the implementation of BinaryHeap#eject and BinaryHeap#insert

Adjust the heap to make it in good shape

Parameters:

  • direction (Symbol) (defaults to: :top_down)

    direction of adjustment, one of [:top_down, bottom_up]

Returns:


88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# File 'lib/binaryheap.rb', line 88

def adjust(direction = :top_down)
  return if @ary.size < 2
  case direction
    when :top_down
      parent_idx = 0
      until is_good?(parent_idx)
        child_idx = target_child_idx(parent_idx)
        swap(parent_idx, child_idx)
        parent_idx = child_idx
      end
    when :bottom_up
      child_idx = @ary.size - 1
      parent_idx = p_idx(child_idx)
      until child_idx == 0 || @cmp.call(@ary[parent_idx], @ary[child_idx]) >= 0
         swap(parent_idx, child_idx)
         child_idx = parent_idx
         parent_idx = p_idx(child_idx)
      end 
    else
      raise ParameterError.new("invalid direction type")
  end
  self
end

#dataObject

Return the underlying Aarray data


80
81
82
# File 'lib/binaryheap.rb', line 80

def data
  @ary
end

#ejectObject

Eject the top(max or min) element of the heap (heap will be adjusted automatically)

Returns:

  • (Object)

    the ejected element


55
56
57
58
59
60
61
62
63
64
# File 'lib/binaryheap.rb', line 55

def eject
  @mutex.synchronize do
    return nil if @ary.empty?
    e = @ary.first
    @ary[0] = @ary.last
    @ary.pop
    adjust(:top_down)
    e
  end
end

#insert(element) ⇒ BinaryHeap Also known as: push

Insert an element into the heap (heap will be adjusted automatically)

Parameters:

  • element (Object)

    the element to be inserted into the heap

Returns:

  • (BinaryHeap)

    the binary heap instance itself


43
44
45
46
47
48
49
# File 'lib/binaryheap.rb', line 43

def insert(element)
  @mutex.synchronize do
    @ary.push(element) 
    adjust(:bottom_up)
  end
  self
end

#topObject

Return the the top(max or min) element of the heap


67
68
69
# File 'lib/binaryheap.rb', line 67

def top 
  @ary.first
end

#top=(element) ⇒ Object

Note:

in most cases, this method should be used with the BinaryHeap#adjust method

Set the top element of the heap

Parameters:

  • element (Object)

See Also:


75
76
77
# File 'lib/binaryheap.rb', line 75

def top=(element)
  @ary[0] = element
end