Nov-12-2019, 10:09 PM
(This post was last modified: Nov-12-2019, 10:09 PM by Clunk_Head.)
It's been a long time since I made my first heap sort algorithm.
I'm looking for optimization tips for this one that I put together this morning.
I'm looking for optimization tips for this one that I put together this morning.
def get_children(index): l_child = index * 2 return l_child, l_child + 1 def get_lesser_child(heap, index): l_child, r_child = get_children(index) lesser = None size = len(heap) if l_child < size: lesser = l_child if r_child < size and heap[r_child] < heap[l_child]: lesser = r_child return lesser def swap(heap, index_a, index_b): heap[index_a], heap[index_b] = heap[index_b], heap[index_a] def sift(heap, high_index): low_index = 1 lesser_child = get_lesser_child(heap, low_index) while lesser_child and heap[low_index] > heap[lesser_child]: swap(heap, low_index, lesser_child) low_index = lesser_child lesser_child = get_lesser_child(heap, low_index) def heapify(heap): for high_index in range(len(heap) - 1, 0, -1): swap(heap, 1, high_index) sift(heap, high_index) heap = [None, 8, 6, 7, 5, 3, 0, 9] heapify(heap) print(heap)
Output:[None, 0, 3, 6, 5, 9, 7, 8]
I'm thinking about using the new 3.8 walrus in the sift function:def sift(heap, high_index): low_index = 1 while (lesser_child := get_lesser_child(heap, low_index)) and heap[low_index] > heap[lesser_child]: swap(heap, low_index, lesser_child) low_index = lesser_childHas anyone used it? Is it faster?