Heap sort

Questions 1 to 5 of 6

1. 1. Put the steps of one sift down, for the value at index i, in the order they run.

   Use the arrows to put the steps in order.

   1. 1.If the value at i is the largest, stop↑↓
   2. 2.Otherwise swap it with the largest child and repeat from that child's index↑↓
   3. 3.Find the largest of the value at i and its two children↑↓
   4. 4.Look at the children at 2 * i + 1 and 2 * i + 2, skipping any child past the end of the list↑↓
2. 2. Put the steps of heap sort in the order they run.

   Use the arrows to put the steps in order.

   1. 1.Swap index 0 with index end, so the largest value moves to its final place↑↓
   2. 2.Sift down index 0 inside the part of the list from index 0 to end - 1↑↓
   3. 3.Lower end by one and repeat until end is 0↑↓
   4. 4.Sift down each index that has a child, from len(a) // 2 - 1 back to index 0, to build a max-heap↑↓
3. 3. What does this program print? ``python def sift_down(a, i, size): while True: left = 2 * i + 1 right = 2 * i + 2 largest = i if left < size and a[left] > a[largest]: largest = left if right < size and a[right] > a[largest]: largest = right if largest == i: return a[i], a[largest] = a[largest], a[i] i = largest a = [3, 8, 1, 6, 5] for i in range(len(a) // 2 - 1, -1, -1): sift_down(a, i, len(a)) print(a) ``

   [8, 6, 1, 3, 5][3, 8, 1, 6, 5][8, 3, 1, 6, 5][8, 6, 5, 3, 1]
4. 4. This program builds a max-heap and then does one round of heap sort. What does it print? ``python def sift_down(a, i, size): while True: left = 2 * i + 1 right = 2 * i + 2 largest = i if left < size and a[left] > a[largest]: largest = left if right < size and a[right] > a[largest]: largest = right if largest == i: return a[i], a[largest] = a[largest], a[i] i = largest b = [4, 6, 1, 8, 2] for i in range(len(b) // 2 - 1, -1, -1): sift_down(b, i, len(b)) b[0], b[-1] = b[-1], b[0] sift_down(b, 0, len(b) - 1) print(b) ``

   [8, 6, 1, 4, 2][2, 6, 1, 4, 8][6, 2, 1, 4, 8][6, 4, 1, 2, 8]
5. 5. What is the worst-case running time of heap sort on n values?

   O(n log n), because there are about n rounds and each sift does at most about log n swapsO(n squared), because a sift can touch every valueO(n), because each value is swapped only onceO(log n), because a sift follows a single path