Question

Using C++, data structures, C++ STL, inputs and expected outputs are shown below.

Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it can be implemented via an array with property: if a node in the binary tree has index i, then its two children have index 2i, 2i+1 respectively. The following is an example of a Max-Heap: TIT7 [276113159 44148 1519-10) 171-26 [8] [9] [10] Index 1 2 3 4 5 6 7 8 9 10 Value 77 61 5948 19 11 26 15 1 5 There are two main operations on heap: Insert a new key: append new key to the end of the array, and then adjust the heap Pop root node: replace the root by the last node in the array, and then adjust the heap Insert: Initially, 20 20 20 heap size is 5. We insert x in to array[6], and continue swapping the node (x) with its farther node if x > farther.key (adjust) to a o do 13 10 20 S farther node "if x> Pop: Initially replace the root u s heap size is 5. We replace the root node by the last node (x=10) in the array (pop). Then continue swapping the new node (x=10) with the children node if x<child.key (adjust)

Answer 1

#include<bits/stdc++.h>
using namespace std;
class maxheap
{
   int *arr;       //array represent the maxheap
   int size;       //size of heap
   int capacity;       //max capacity of heap
   public:
   maxheap(int c)
   { size=0;       //initially size of heap will be zero
   capacity = c;
   arr = new int[c]; //create new array of size c dynamically
   }
   void adjustheap(int index)//adjust heap from child to parent
   {   while(index>0&&arr[(index-1)/2]<arr[index])//(index-1)/2 represent parent if parent less then current then print
       {swap(arr[index],arr[(index-1)/2]);//swap is inbuilt function it swap the data
           index=(index-1)/2;
       }
      
   }
   void adjustheap_pop(int index)// adjust heap from parent to child
   {   int left_child = 2*index+1; //index of left child
        int right_child = 2*index+2; //index of right child
       int maximum = index; //maximum contain the index of element that is greater then root and maximum of left and right child
       if (left_child < size && arr[left_child] > arr[maximum])
           maximum = left_child;
       if (right_child < size && arr[right_child] >arr[maximum])
            maximum = right_child;
        if (maximum != index)
           {
            swap(arr[index], arr[maximum]);
           //cout << arr[index] << arr[maximum]<<endl;
           adjustheap_pop(maximum); //recursive call the same function
            }
         
      
      
   }
   void insert(int element)//use for insert the element
   {
       arr[size++]=element;
       adjustheap(size-1);  
   }
   int pop()//pop the element
   {
       int number=arr[0];
       if(size==1)//if size is 0 then return and decrease the size
       {size--;
       return number;
       }
       else//swap root and last child and decrese the size and adjust the heap
       {arr[0]=arr[--size];
       adjustheap_pop(0);
       }
       return number;// return the root
   }
   int sum()//calculate the sum
   {
       int sm=0;
       for(int i=0;i<size;i++)
       sm+=arr[i];
       return sm;  
   }
   void print1()// it is for printing the array if you want then use
   {
       for(int i=0;i<size;i++)
       cout << arr[i] << " ";

   }
  
};
int main()
{
   // if you want multiple test case then use this otherwise remove t and while loop
   int t;
   cin >> t;
   while(t--)
   {
   //I am taking capacity of heap as n because if all operation of insert then its highest size become n.
   int n;
   cin >> n;
   maxheap mh(n);
   while(n--)
   {
       char ch;
       int element;
       cin >> ch;
       if(ch=='a')
       {cin >> element;
       mh.insert(element);
       }
       else if(ch=='p')
       {mh.pop();
       //cout<< mh.pop()<<"\n";
       }
       else if (ch=='r')
       {
       cout<< mh.sum()<<"\n";
       //mh.print1();
       }

   }
   }
   //please rate it   
}

Thu 19:29 Terminal - Activities najss@najss-Inspiron-3543: ~ File Edit View Search Terminal Help 5 (base) najss@najss- Inspiron - 3543 : ~$ gedit q1.cpp ^C |(base) najss@najss-Inspiron-3543 : ~$ g++ q1.cpp (base) najss@najss-Inspiron - 3543 : ~$ ./a.out AC (base) najss@najss - Inspiron - 3543 : ~$ gedit q1.cpp AC (base) najss@najss- Inspiron- 3543 : ~$ g++ q1.cpp (base) najss@najss-Inspiron - 3543 : ~$ ./a.out 13 а 61 a 1 a 77 a 19 a 26 а 15 a 59 a 5 a 48 а 11 184 a 5 a 4 р 4 a 2 a 3 р r |(base) najss@najss - Inspiron- 3543 : ~$