TVK practice example
Data Structure: heap · C
This function must restore a min-heap when only a[i] may be out of place. Which expression belongs in the blank?
#include <stdio.h>
void sift_down(int a[], int n, int i) {
while (1) {
int small = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] < a[small]) small = l;
if (r < n && ________) small = r;
if (small == i) break;
int t = a[i]; a[i] = a[small]; a[small] = t;
i = small;
}
}
int main(void) {
int a[] = {5, 1, 2, 9, 7, 3, 4};
sift_down(a, 7, 0);
for (int k = 0; k < 7; k++) printf("%d ", a[k]);
printf("\n");
return 0;
}- A.a[r] < a[small]
- B.a[r] < a[i]
- C.a[r] > a[small]
- D.a[r] < a[l]
- E.small == l
Answer and working
Answer: A
- The rule for each pass: small holds the index of the smallest value seen so far among the parent and its children. The right child must be compared with that value, which is a[small].
- Option B compares with the parent only, so on 5 1 2 it picks 2 even though 1 is smaller. Option D ignores the parent, so it can swap a parent that was already smaller than both children.
- On this input option A gives 1 5 2 9 7 3 4: every parent is at most its children. The other four options leave a parent larger than a child.
Output with the right option in the blank
1 5 2 9 7 3 4| Option | What happened when we ran it |
|---|---|
| A | 1 5 2 9 7 3 4 (a valid min-heap) |
| B | 2 1 4 9 7 3 5 (not a heap: 2 is above 1) |
| C | 2 1 4 9 7 3 5 (not a heap: 2 is above 1) |
| D | 1 7 2 9 5 3 4 (not a heap: 7 is above 5) |
| E | 2 1 4 9 7 3 5 (not a heap: 2 is above 1) |