Assume you have been given an array A (indexed from 1), an integer m, and an int
ID: 3760434 • Letter: A
Question
Assume you have been given an array A (indexed from 1), an integer m, and an integer n. The integer m represents the total number of elements allocated for array A. The integer n indicates how many values are currently stored at the beginning of array A (in elements 1 through n). You can assume that n<=m
Write a function isHeap(A, n) in pseudocode which explores the first n elements of array A and returns TRUE if the first n elements contain a min heap, or FALSE if they do not. This function should execute in O(n) time. Hint: Make sure function doesn’t explore the array past the first n elements.
Explanation / Answer
isHeap(A,n)
int i = 0;
Bool isHeap = true;
while(i <= n){
if(2*i - 1 < n && A[2*i - 1] < A[i]){
isHeap = false;
break;
}
if(2*i + 1 < n && A[2*i + 1] < A[i]){
isHeap = false;
break;
}
}
return isHeap;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.