Skip to content

Instantly share code, notes, and snippets.

@zackster

zackster/max-heap.rb

Last active Feb 14, 2019
Embed
What would you like to do?
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
You can’t perform that action at this time.