Last active
July 14, 2019 06:40
-
-
Save pdkproitf/025b926f4f112ffe5eff550e3bfad551 to your computer and use it in GitHub Desktop.
Implement Heap Sort 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
module MinHeapSortV1 | |
module_function | |
def heap_sort(array) | |
n = array.length | |
a = [nil] + array | |
(n / 2).downto(1) { |i| heapify(a, i, n) } | |
while n > 1 | |
printf "#{a}\n" | |
a[1], a[n] = a[n], a[1] | |
n -= 1 | |
heapify(a, 1, n) | |
end | |
a.drop(1) | |
end | |
def heapify(array, parent, limit) | |
root = array[parent] | |
while (child = 2 * parent) <= limit | |
child += 1 if child < limit && array[child] < array[child + 1] | |
break if root >= array[child] | |
array[parent], parent = array[child], child | |
array[parent] = root | |
end | |
end | |
def sort(arr) | |
puts '------------------------------MIN HEAP SORT V1 O(nlogn)--------------------------' | |
print heap_sort(arr) | |
puts '' | |
end | |
end | |
module MinHeapSort | |
extend self | |
@heap = Array.new | |
@sorted = Array.new | |
def create_heap(arr) | |
arr.each_with_index { |num, index| insert(index, num) } | |
@heap | |
end | |
def insert(index, node) | |
@heap[index] = node | |
bubble_up(index) | |
end | |
def bubble_up(index) | |
parent_index = (index - 1) / 2 | |
child_index = index | |
return if child_index.zero? | |
if @heap[child_index] < @heap[parent_index] | |
swap(parent_index, child_index) | |
bubble_up(parent_index) | |
end | |
end | |
def swap(parent_index, child_index) | |
temp = @heap[child_index] | |
@heap[child_index] = @heap[parent_index] | |
@heap[parent_index] = temp | |
end | |
def extract_min | |
while @heap.length > 0 | |
@sorted << @heap.first | |
swap(0, @heap.length - 1) | |
@heap.delete_at(@heap.length - 1) | |
sink_down(0) | |
end | |
@sorted | |
end | |
def sink_down(parent_index) | |
smallest_index = parent_index | |
left_child = 2 * parent_index + 1 | |
right_child = 2 * parent_index + 2 | |
smallest_index = left_child if @heap[left_child] && @heap[left_child] < @heap[smallest_index] | |
smallest_index = right_child if @heap[right_child] && @heap[right_child] < @heap[smallest_index] | |
return if smallest_index == parent_index | |
swap(parent_index, smallest_index) | |
sink_down(smallest_index) | |
end | |
def sort(arr) | |
puts '------------------------------MIN HEAP SORT O(nlogn)--------------------------' | |
print create_heap(arr) | |
puts '' | |
print extract_min | |
puts '' | |
end | |
end | |
arr = [3,7,8,4,10,16,2,1,12] | |
MinHeapSortV1.sort(arr.dup) | |
MinHeapSort.sort(arr.dup) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment