Implementing a max-heap in Ruby (with heapsort)

Here at Code For Cash we figure that if we are going to be asking candidates to be proficient in data structures and algorithms, we should be as well.

Here is an example of max heap and heapsort implementation in Ruby.

 

# O(n)
def heapify(arr)
last_element_index = arr.count1
idx = parent_index(last_element_index)
while idx >= 0
arr = fix(arr, idx)
idx -= 1
end
arr
end
def fix(arr, idx)
if leaf_node?(arr, idx)
return arr
end
if satisfies_heap_property?(arr, idx)
return arr
end
swap = bigger_child(arr, idx)
arr[idx], arr[swap] = arr[swap], arr[idx]
fix(arr, swap)
end
def bigger_child(arr, idx)
if arr[right_child(idx)]
if arr[right_child(idx)] > arr[left_child(idx)]
right_child(idx)
else
left_child(idx)
end
else
left_child(idx)
end
end
def satisfies_heap_property?(arr, idx)
if arr[right_child(idx)]
arr[right_child(idx)] <= arr[idx] && arr[left_child(idx)] <= arr[idx]
else
arr[left_child(idx)] <= arr[idx]
end
end
def leaf_node?(arr, idx)
arr[right_child(idx)].nil? && arr[left_child(idx)].nil?
end
def right_child(idx)
idx * 2 + 2
end
def left_child(idx)
idx * 2 + 1
end
def parent_index(idx)
((idx1) / 2.0).floor
end
def insert(el, arr)
arr << el
percolate_up(arr)
end
def percolate_up(arr)
idx = arr.count1
while has_parent?(idx)
swap = parent_index(idx)
if arr[idx] > arr[swap]
arr[swap], arr[idx] = arr[idx], arr[swap]
end
idx = parent_index(idx)
end
arr
end
def has_parent?(idx)
((idx1)/ 2).floor >= 0
end
# O(log n)
def delete_max(arr)
swap = arr.count1
arr[0], arr[swap] = arr[swap], arr[0]
arr.pop
fix(arr, 0)
end
# n elements * delete_max => O(n log n)
def heap_sort(arr)
ret = []
while arr.count > 0
ret << arr[0]
arr = delete_max(arr)
end
ret
end
arr = heapify([1,2,3,4,5,6,7,8,9,10])
puts arr.join(',')
arr = insert(11, arr)
puts arr.join(',')
puts "max element: #{arr[0]}"
arr = delete_max(arr)
puts arr.join(',')
puts "heap sorting: #{heap_sort(arr).join(',')}"

view raw
max-heap.rb
hosted with ❤ by GitHub