|
You are given a pointer to a node of a min heap........
Microsoft Interview Questions and Answers
(Continued from previous question...)
119. You are given a pointer to a node of a min heap........
Question:
You are given a pointer to a node of a min heap. The value of this node changes. Write a function that fixes the min heap.
maybe an answer:
KeepMinHeap(int *a, int len, int i, int val) {
// a is the underlying array of the min heap
// len is the length of the min heap
// i is the index of the element whose value is changed, i = 1,...,len
// val is the new value of the i-th element
old = a[i];
a[i] = val;
if (old == val) {
return;
} else if (old > val) {
SWAP_UPWARDS(a, len, i);
} else {
SWAP_DOWNWARDS(a, len, i);
}
}
SWAP_UPWARDS(int *a, int len, int i) {
while ( i/2 > 0 && a[i/2] > a[i] ) {
swap(a[i/2], a[i]);
i = i/2;
}
}
SWAP_DOWNWARDS(int *a, int len, int i) {
// the code below is also called HEAPIFY
int left = i * 2;
int right = i * 2 + 1;
int min = i;
if (left <= len && a[min] > a[left]) {
min = left;
}
if (right <= len && a[min] > a[right]) {
min = right;
}
if (min == i) {
return;
} else {
swap(a[i], a[min]);
return SWAP_DOWNWARDS(a, len, min);
}
}
(Continued on next question...)
Other Interview Questions
| 