Do the first half of heap sort, and look at the array it produces.
What to build
A program that turns an array into a max-heap without using a second array.
Requirements
- Write a
sift_downfunction. - Call it for each parent, from index
n / 2 - 1down to 0. - When the two children are equal, swap with the left one.
- Print the array after building the heap.
Input
The first line has n. The second line has the n numbers.
Output
The array after the heap is built, numbers separated by spaces.
Constraints
1 ≤ n ≤ 200.
Example
Input:
5
4 10 3 5 1
Output:
10 5 3 4 1
Why it works
By the time an index is sifted down, both of its subtrees are already heaps, so one sift repairs the whole subtree. Most nodes are near the bottom and move very little, which makes the whole build O(n).
Examples
Example 1 · Input
5 4 10 3 5 1
Expected output
10 5 3 4 1
Example 2 · Input
1 7
Expected output
7
Hints
Hint 1
The last parent is at index `n / 2 - 1`. Start there and go backwards to index 0.
Hint 2
Sifting down compares an item with its two children, swaps with the larger child if needed, and continues from there.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
void sift_down(int a[], int n, int i) {
while (1) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest == i) return;
int t = a[i];
a[i] = a[largest];
a[largest] = t;
i = largest;
}
}
int main(void) {
int n, a[200];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}