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.
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(',')}" |
Code For Cash blog 