One of the data structures that I came across was a heap (as in heapsort if you've forgotten). A heap is a binary tree data structure that has the property that the parent is smaller for a min-heap or larger for a max-heap than its children. They can be used for priority queues as the minimum or maximum is always at the top of the heap or for sorting assuming that you a) take the top element and then b) recalculate the tree.

The code here follows Skiena's pretty closely excepting he starts his array at 1 and I use the more natural (for me anyway) 0 start. This code also implements only a min-heap, but you should take a bit of time to see if you can figure out how to make it either a min-heap or a max-heap as an initialization parameter. A couple of other things aren't that pretty (

`extract_min!`

in particular bugs me), but mostly it's not bad and is straight forward. So ... here's the code

class Heap

def initialize(a)

@q = []

a.each { |v| insert(v) } if a

end

def parent(n)

n == 0 ? -1 : (n-1) / 2

end

def young_child(n)

(2 * n) + 1

end

def insert(v)

@q << v

bubble_up(@q.size-1)

end

def bubble_up(n)

return if parent(n) == -1 # Root of heap, no parent

if @q[parent(n)] > @q[n]

swap(n, parent(n))

bubble_up(parent(n))

end

end

def swap(n, pn)

@q[n], @q[pn] = @q[pn], @q[n]

end

def min

@q.first

end

def extract_min!

m, @q[0] = @q.first, @q.last

@q.pop

bubble_down(0)

m

end

def bubble_down(n)

c = young_child(n)

min_index = n

0.upto(1) { |i| min_index = c+i if ((c+i) <= @q.size-1) &&(@q[min_index] > @q[c+i]) }

if (min_index != n)

swap(n, min_index)

bubble_down(min_index)

end

end

def sort!

a = []

while v = extract_min! do a << v end

a

end

end

h = Heap.new([12, 14, 6, 10, 8, 27, 1, 4, 9])

puts "extract_min! = #{h.extract_min!}"

puts "extract_min! = #{h.extract_min!}"

puts "extract_min! = #{h.extract_min!}"

puts "extract_min! = #{h.extract_min!}"

puts "min = #{h.min}"

puts "min = #{h.min}"

puts "sort! = #{h.sort!}"

Let me know if you have any questions or comments and if you make improvements, post those too.

## No comments:

## Post a Comment