Question

• Implement the algorithm Build Heap in C (or C++). Algorithm buildHeap (heap, size) set walker to 1 loop (walker < size) reheapUp (heap, walker) increment walker end loop • Write a program to test your program using a random integer array of size 30. Print the arrays before and after building the heap.

Answer 1

//C++ code

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

//Creating a min Heap

void reheapUp(int arr[] , int index) {
       if(index==0)return;
       int parent=(index)/2;
       if(arr[index] < arr[parent]) {
           int temp=arr[index];
           arr[index]=arr[parent];
           arr[parent]=temp;
           reheapUp(arr , parent);
       }
   }
  
   void display(int arr[] , int size) {
       for(int i=0;i<size;i++) {
           cout<<arr[i]<<" ";
       }
  
   }
  
   void buildHeap(int arr[] , int size){
       int walker = 1;
       while(walker < size){
           reheapUp(arr , walker);
           walker++;
       }
   }
  
int main(){
   srand(time(NULL));
   int size = 30;
   int heap[size];
  
   for(int i=0;i<size;i++){
       heap[i] = rand()%100;
   }
  
   cout<<"Heap before build Heap\n";
   display(heap , size);
  
   buildHeap(heap ,size);
   cout<<"\n\nHeap after build Heap\n";
   display(heap , size);
  
   return 0;
}