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

#data ⇒ Object

Return the underlying Aarray data


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

def data
	@ary
end

#eject ⇒ Object

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

#top ⇒ Object

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