C++ style code writing please! and if possible, due friday at midnight please!!!

Question

C++ style code writing please! and if possible, due friday at midnight please!!!

Here's the Code for the assignment: -- the professor gave us coe and told us to add more to it. he wasnts the maxheap to work 100% pefectly.

Question 1 (100pt] Implement a MaxHeap and HeapSort. We are providing some sample code and input files: public/ main method to try your implementation demo .cpp K- folder with several sample inputs inputs K- maxheap.cpp the actual implementation only file you have to modify) max heap. hpp header file The code provided follows closely the implementation in the textbook. To compile, run g++ -o heapsort demo.cpp maxheap. cpp To test your implementation with a sample input file, run /heapsort inputs/input.10.1 This will test a few methods (you need to check the maxheap after each step manually), and run heapsort (the code will check whether the output is sorted automatically) To test your implementation with all sample files with one command, tun time for f in inputs/input.10 do echo sf: /heapsort sf: done The command time will let you know how long it took to run the code. You may want to store the output in a file so that you can look at it carefully time for f in inputs/input.10 do echo $f /heapsort $f; done output Grading If you implement all the methods in maxheap. cpp properly (i.e., the demo works for any sample input), you will get 100. You also have a few opportunities to earn extra credit: Implement and test additional methods. For example, implement and test deleteMin, decreaseKey remove, etc. Optimize your code to run fast. The fastest submissions (top 5) will receive extra credit

Explanation / Answer

#include<iostream>
#include<vector>
//#include<algorithm>
using namespace std;

class Maxheap
{
private:
   vector<int>arr;
public:
   int size()
   {
       return arr.size();
   }

   bool empty()
   {
       return (size()== 0);
   }

   int left(int parent)
   {
       return (2*parent + 1);
   }

   int right(int parent)
   {
       return (2*parent + 2);
   }

   int parent(int child)
   {
       return (child - 1 )/ 2;
   }

   void insert(int element)
   {
       arr.push_back(element); // add new element to the end of vector

       int index = size() - 1;
       percolateUp(index);
   }

   int deleteMax()
   {
       arr[0] = arr.back();
       arr.pop_back();
       percolateDown(0);
   }

   void display()
   {
       vector<int>::iterator it;
       cout << "Maxheap:- ";
       for (it = arr.begin(); it != arr.end(); ++it)
           cout << *it << " ";
    }

   void percolateUp(int index)
   {
       if (index && arr[parent(index)] < arr[index])
       {
           swap(arr[index], arr[parent(index)]);
           percolateUp(parent(index));
       }
      
   }

   void percolateDown(int index)
   {
       int left_ind = left(index);
       int right_ind = right(index);

       int largest = index;

       if (left_ind < size() && arr[left_ind] > arr[index])
           largest = left_ind;

       if (right_ind < size() && arr[right_ind] > arr[largest])
           largest = right_ind;

       if (largest != index)
       {
           swap(arr[index], arr[largest]);
           percolateDown(largest);
       }
   }

   void Heapify(int i)
   {
       int left_ind = left(i);
       int right_ind = right(i);

       int smallest = i;

       if (left_ind < size() && arr[left_ind] < arr[i])
           smallest = left_ind;

       if (right_ind < size() && arr[right_ind] < arr[smallest])
           smallest = right_ind;

       if (smallest != i)
       {
           swap(arr[i], arr[smallest]);
           Heapify(smallest);
       }
   }

   void buildHeap(vector<int> A, int n)
   {
       vector<int>::iterator it;
       for (it = A.begin(); it != A.end(); it++)
           arr.push_back(*it);
   }
};

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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