How do I implement this heap in linear time? #include <iostream> #include <stdli

Question

How do I implement this heap in linear time?

#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cassert>
using namespace std;

//add CODE here
//Do this in time LINEAR in length!!!

void Heapify(int *anArray, int length){
  
};

//stop CODE here

int main() {
//Do not edit main
srand(time(NULL));
int myarray[10000];
for (int i = 0; i < 10000; i++){
myarray[i] = rand();
}
Heapify(myarray, 10000);
for (int i = 0; 2*i+2 < 10000; i++){
assert(myarray[i] > myarray[2*i + 1]);
assert(myarray[i] > myarray[2*i + 2]);
}
cout << "All tests pass" << endl;
}

Explanation / Answer

#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cassert>
using namespace std;
//add CODE here
//Do this in time LINEAR in length!!!

void Heapify(int *anArray, int length){
int i, c, root, temp;
for (i = 1; i < length; i++) /*From second element to last element.*/
{
c = i;               /*Copy ith element to c.*/
do
{
root = (c - 1) / 2; /*Calculate the parent.*/   
if (anArray[root] < anArray[c]) /*If parent value is less than the child., Exchange.*/
{
temp = anArray[root];
anArray[root] = anArray[c];
anArray[c] = temp;
}
c = root;
}while (c != 0);
}
};

//stop CODE here
int main() {
//Do not edit main
srand(time(NULL));
int myarray[10000];
for (int i = 0; i < 10000; i++){
myarray[i] = rand();
}
Heapify(myarray, 10000);
for (int i = 0; 2*i+2 < 10000; i++){
assert(myarray[i] > myarray[2*i + 1]);
assert(myarray[i] > myarray[2*i + 2]);
}
cout << "All tests pass" << endl;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.