Java Given the below MaxPriorityqueue class, complete the below insert method su

Question

Java

Given the below MaxPriorityqueue class, complete the below insert method such that after inserting the given integer k, the array pq is a max heap. Also, indicate the worst-case runtime of your implementation. You can use the exch method and/or write additional helper methods if needed. public class MaxPriorityQueue {private int[] pq;//store items at indices 1 to N, max heap private int N;//number of items on priority queue public MaxPriorityQueue() {pq = new int[1025]; N = 0;} public void insert(int x) {//T0D0} private void exchCint i, int j) {int swap = pq[i]; pq[i] = pq[j] pq[j] = swap;}}

Explanation / Answer

public void insert(int x)
{
   pq[N]=x;//inserting into maxheap
   N++;//incrementing count variable
   int k=N-1,l;
   //maxheapying
  
   while(k>0)
   {
       l=(k-1)/2;//finding parent
       if(pq[l]>pq[k])//if max heap property followed
           break;//then break
       else//if not followed
       {//swapping
           exch(l,k);
           k=l;  
       }
          
   }
}
//complexity of this method at worst is O(logN)..where N is number of nodes in heap

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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