language is C++ 4) Program Heap Write the code to implement a complete binary he

Question

language is C++

4) Program Heap

Write the code to implement a complete binary heap using an array ( Not a vector ). Code for Max heap.

Implement: AddElement, GetMax, HeapSort, ShuffleUp, ShuffleDown, etc

Set array size to 31 possible integers.

Add 15 elements 1,3,27,22,18,4,11,26,42,19,6,2,15,16,13

Have a default constructor that initializes the array to zeros..

The data in the heap will be double datatype.

5) Program Template

Convert Program 4 to template, test with integers, double and char

what I got until now (from another help) is this code

#include "stdafx.h"
#include <iostream>
#include <conio>
using namespace std;
double getmax(double[], int);
void heapsort(double[], int);
void max_heapify(double *k, int i, int n)
{
   int j;
   double temp = k[i];
   j = 2 * i;
   while (j <= n)
   {
       if (j < n && k[j + 1] > k[j])
           j = j + 1;
       if (temp > k[j])
           break;
       else if (temp <= k[j])
       {
           k[j / 2] = k[j];
           j = 2 * j;
       }
   }
   k[j / 2] = temp;
   return;
}
void build_maxheap(double *k, int n)
{
   int i;
   for (i = n / 2; i >= 1; i--)
   {
       max_heapify(k, i, n);
   }
}
int main()
{
   int n, i, x;
   double max;
   cout << "enter no of elements of array ";
   cin >> n;
   double k[20];
   for (i = 1; i <= n; i++)
   {
       cout << "enter element" << (i) << endl;
       cin >> k[i];
   }
   build_maxheap(k, n);
   cout << "Max Heap ";
   for (i = 1; i <= n; i++)
   {
       cout << k[i] << endl;
   }
   heapsort(k, n);
   max = getmax(k, n);
   cout << " max is " << max;
   cout << " Sorted Array ";
   for (i = 1; i <= n; i++)
   {
       cout << k[i] << endl;
   }
   getch();
}
void heapsort(double *k, int n)
{
   int i, temp;
   for (i = n; i >= 2; i--)
   {
       temp = k[i];
       k[i] = k[1];
       k[1] = temp;
       max_heapify(k, 1, i - 1);
   }
}
double getmax(double *k, int n)
{
   double max;
   max = 0;
   for (int i = 1; i <= n; i++)
   {
       if (max<k[i]) max = k[i];

   }

   return max;
}

please help me fix it and make another code with a templet

Explanation / Answer

//Without using template
#include<iostream>
#include<iomanip>
using namespace std;
class heap
{
private:
   int size;
   int heaparray[];
public:
   heap()//default constructor
   {
       size=31;
       for(int i=1;i<=size;i++)
       {
           heaparray[i]=0;//initialize array to Zeros
       }
       cout<<"Default heap elements are-->";
           for(int i=1;i<=size;i++)
           {
               cout<<heaparray[i]<<setw(5);
           }
           cout<<endl;
   }
   int getsize()
   {
       return size;
   }
   void AddElement()
   {
       //add fifteen elements to array.
       int num;
       cout<<"Enter element in heap";
       for(int i=1;i<=15;i++)
       {
           cin>>num;
       heaparray[i]= num;
       }
   }
   void max_heapify(int *k,int i, int n)
   {
       int j;
double temp = k[i];
j = 2 * i;
while (j <= n)
{
if (j < n && k[j + 1] > k[j])
j = j + 1;
if (temp > k[j])
break;
else if (temp <= k[j])
{
k[j / 2] = k[j];
j = 2 * j;
}
}
k[j / 2] = temp;
return;
   }
   void min_heapify(int *a,int i,int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
   void minheap()//build mean heap
{
int i;
for(i = 15/2; i >= 1; i--)
{
       min_heapify(heaparray,i,15);
}
   cout<<"print min heap-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
       cout<<endl;
}
   int GetMax()
   {
       double max;
max = 0;
for (int i = 1; i <= 15; i++)
{
       if (max<heaparray[i]) max = heaparray[i];
}
return max;
   }
   void maxheap()
   {
       for(int i=15/2;i>=1;i--)
       {
           max_heapify(heaparray,i,15);
       }
       cout<<"print max heap-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
       cout<<endl;
   }
   void HeapSort()
   {
       int temp;
for(int i=15;i>=2;i--)
   {
       temp=heaparray[i];
       heaparray[i]=heaparray[1];
       heaparray[1]=temp;
       max_heapify(heaparray,1,i-1);
   }
   }
   void printHeap()
   {
       HeapSort();
       cout<<"The sorted heap is-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
   }
};
void main()
{

   heap hp;
   int heapSize=hp.getsize();
   hp.AddElement();
   hp.maxheap();//build max heap;
   hp.minheap();//build min heap;
   hp.printHeap();//print sorted heap
   cout<<endl<<"Heap size is -->"<<hp.getsize();
   cout<<endl<<"Maximum value of heap -->"<<hp.GetMax();
}

// Using Template

#include<iostream>
#include<iomanip>
using namespace std;
template <class T>

class heap
{
private:
   int size;
   T heaparray[];
public:
   heap()//default constructor
   {
       size=31;
       for(int i=1;i<=size;i++)
       {
           heaparray[i]=0;//initialize array to Zeros
       }
       cout<<"Default heap elements are-->";
           for(int i=1;i<=size;i++)
           {
               cout<<heaparray[i]<<setw(5);
           }
           cout<<endl;
   }
   int getsize()
   {
       return size;
   }
   void AddElement()
   {
       //add fifteen elements to array.
       T num;
       cout<<"Enter element in heap";
       for(int i=1;i<=15;i++)
       {
           cin>>num;
       heaparray[i]= num;
       }
   }
   void max_heapify(int *k,int i, int n)
   {
       int j;
double temp = k[i];
j = 2 * i;
while (j <= n)
{
if (j < n && k[j + 1] > k[j])
j = j + 1;
if (temp > k[j])
break;
else if (temp <= k[j])
{
k[j / 2] = k[j];
j = 2 * j;
}
}
k[j / 2] = temp;
return;
   }
   void min_heapify(int *a,int i,int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
   void minheap()//build mean heap
{
int i;
for(i = 15/2; i >= 1; i--)
{
       min_heapify(heaparray,i,15);
}
   cout<<"print min heap-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
       cout<<endl;
}
   T GetMax()
   {
       T max;
max = 0;
for (int i = 1; i <= 15; i++)
{
       if (max<heaparray[i]) max = heaparray[i];
}
return max;
   }
   void maxheap()
   {
       for(int i=15/2;i>=1;i--)
       {
           max_heapify(heaparray,i,15);
       }
       cout<<"print max heap-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
       cout<<endl;
   }
   void HeapSort()
   {
       T temp;
for(int i=15;i>=2;i--)
   {
       temp=heaparray[i];
       heaparray[i]=heaparray[1];
       heaparray[1]=temp;
       max_heapify(heaparray,1,i-1);
   }
   }
   void printHeap()
   {
       HeapSort();
       cout<<"The sorted heap is-->";
       for(int i=1;i<=15;i++)
       {
           cout<<heaparray[i]<<setw(5);
       }
   }
};
void main()
{

   heap<int> hp;
   int heapSize=hp.getsize();
   hp.AddElement();
   hp.maxheap();//build max heap;
   hp.minheap();//build min heap;
   hp.printHeap();//print sorted heap
   cout<<endl<<"Heap size is -->"<<hp.getsize();
   cout<<endl<<"Maximum value of heap -->"<<hp.GetMax();
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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