Write BuildHeap for a min-heap stored in an array (children of i at 2i + 1 and 2i + 2). Read n and n integers and:
- say whether the input already is a min-heap;
- build a heap bottom-up (Floyd):
siftDownevery internal node from index n/2 − 1 down to 0 — print the array and the number of swaps; - build a heap from the same input by inserting one by one (
siftUpfor i = 1 … n − 1) — print the array and the swaps; - heap-sort the first heap in place (swap the root with the last element, shrink, sift down), which leaves the array in descending order.
For the input
7
9 4 7 1 2 6 3
the program prints
Input is a min-heap: false
Bottom-up heapify: [1, 2, 3, 4, 9, 6, 7] swaps 4
Insert one by one: [1, 2, 3, 9, 4, 7, 6] swaps 6
Both are min-heaps: true
Heap sort (descending): [9, 7, 6, 4, 3, 2, 1]