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.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(',')}" |
