Skip to content

Instantly share code, notes, and snippets.

@ser1zw
Created November 12, 2018 11:32
Show Gist options
  • Save ser1zw/cd4b27f0553bd1c3dfd183c1260110b6 to your computer and use it in GitHub Desktop.
Save ser1zw/cd4b27f0553bd1c3dfd183c1260110b6 to your computer and use it in GitHub Desktop.
ヒープソートの練習
# ヒープソートの練習
#
# 参考
# - https://ufcpp.net/study/algorithm/col_heap.html
# - https://ufcpp.net/study/algorithm/sort_heap.html
def make_heap(array, last_index)
while (last_index > 0)
parent = ((last_index - 1) / 2).floor
break unless (array[last_index] > array[parent])
array[last_index], array[parent] = array[parent], array[last_index]
last_index = parent
end
end
def pop_heap(array, last_index)
# ヒープなので、最大値はルートノード
max = array[0]
# 再ヒープ
array[0] = array[last_index]
parent = 0
loop {
child = 2 * parent + 1
break unless child < last_index
# 左右の子のうち、大きいほうを child にする(右の子のインデックス = 左の子のインデックス + 1 なので)
child += 1 if ((child + 1) < last_index) && (array[child] < array[child + 1])
if (array[parent] < array[child])
array[child], array[parent] = array[parent], array[child]
end
parent = child
}
max
end
def heap_sort(array)
1.upto(array.size - 1) { |i|
make_heap(array, i)
}
(array.size - 1).downto(0) { |i|
array[i] = pop_heap(array, i)
}
end
a = [3, 1, 4, 1, 5, 9, 2]
# a = [3, 1, 4, 1, 5, 9, 2, 6]
pp a
heap_sort(a)
pp a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment