Implementation of max-heap in Ruby
# O(n) | |
def heapify(arr) | |
last_element_index = arr.count - 1 | |
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) | |
((idx - 1) / 2.0).floor | |
end | |
def insert(el, arr) | |
arr << el | |
percolate_up(arr) | |
end | |
def percolate_up(arr) | |
idx = arr.count - 1 | |
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) | |
((idx - 1)/ 2).floor >= 0 | |
end | |
# O(log n) | |
def delete_max(arr) | |
swap = arr.count - 1 | |
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(',')}" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment