Implementation of max-heap in Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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