class HeapSort
Public Class Methods
create_heap(data)
click to toggle source
# File lib/compare-sort.rb, line 268 def self.create_heap(data) for i in 0..(data.length-1) # if they are greater than their parent swap them current_index = i current_value = data[i] parent_index = get_parent(i) while parent_index != nil && current_value > data[parent_index] parent_value = data[parent_index] # swap data[parent_index] = current_value data[current_index] = parent_value #reset values current_index = parent_index parent_index = get_parent(current_index) end end return data end
find_larger_child(parent_index, heap, number_sorted)
click to toggle source
# File lib/compare-sort.rb, line 329 def self.find_larger_child(parent_index, heap, number_sorted) children_i = [] l_child_i = left_child_index(parent_index) r_child_i = right_child_index(parent_index) if l_child_i < (heap.length - number_sorted) children_i << l_child_i end if r_child_i < (heap.length - number_sorted) children_i << r_child_i end return nil if children_i.length == 0 max_child_i = children_i[0] children_i.each do |index| max_child_i = index if heap[index] > heap[max_child_i] end return max_child_i end
get_parent(index)
click to toggle source
# File lib/compare-sort.rb, line 291 def self.get_parent(index) parent_index = (index-1)/2 return nil if parent_index < 0 return parent_index end
left_child_index(parent_index)
click to toggle source
# File lib/compare-sort.rb, line 373 def self.left_child_index(parent_index) return 2*parent_index + 1 end
right_child_index(parent_index)
click to toggle source
# File lib/compare-sort.rb, line 377 def self.right_child_index(parent_index) return 2*parent_index + 2 end
run(data)
click to toggle source
# File lib/compare-sort.rb, line 256 def self.run(data) return data if data.length <= 1 # create heap heap = self.create_heap(data) # then sort sorted_data = self.sort_heap(heap) return sorted_data end
sort_heap(heap)
click to toggle source
# File lib/compare-sort.rb, line 297 def self.sort_heap(heap) number_sorted = 0 while number_sorted < heap.length # switch the root and the last element # puts "swapping root: #{heap[0]} with bottom: #{heap[-1-number_sorted]}" heap[0], heap[-1-number_sorted] = heap[-1-number_sorted], heap[0] # p heap number_sorted += 1 current_index = 0 current_value = heap[0] while !self.valid_parent(current_index, heap, number_sorted) # find highest valid child index max_child_i = self.find_larger_child(current_index, heap, number_sorted) # swap them heap[max_child_i], heap[current_index] = heap[current_index], heap[max_child_i] # reset values current_index = max_child_i end end return heap end
valid_parent(parent_index, heap, number_sorted)
click to toggle source
# File lib/compare-sort.rb, line 355 def self.valid_parent(parent_index, heap, number_sorted) parent_value = heap[parent_index] valid = true l_child_i = left_child_index(parent_index) r_child_i = right_child_index(parent_index) if l_child_i < (heap.length - number_sorted) && heap[l_child_i] > heap[parent_index] valid = false end if r_child_i < (heap.length - number_sorted) && heap[r_child_i] > heap[parent_index] valid = false end return valid end