//header //driver #include <iostream> using namespace std; #include \"header.h\"

Question

//header

//driver

#include <iostream>
using namespace std;
#include "header.h"

int main()
{
   priorityQueue myqueue; //class object
  
   myqueue.empty();
  
   cout << "After inserting 59 Priority Queue has" << endl;
   myqueue.insert(59); //Insert value into queue
   cout << endl << endl;

  
   cout << "After inserting 41 Priority Queue has" << endl;
   myqueue.insert(41);
   cout << endl << endl;

  
   cout << "After inserting 25 Priority Queue has" << endl;
   myqueue.insert(25);
   cout << endl << endl;

  
   cout << "After inserting 12 Priority Queue has" << endl;
   myqueue.insert(12);
   cout << endl << endl;

  
   cout << "After inserting 91 Priority Queue has" << endl;
   myqueue.insert(91);
   cout << endl << endl;

  
   cout << "After extracting the minimum value Priority Queue has" << endl;
   myqueue.extractMin();
   cout << endl << endl;

  
   cout << "After inserting 34 Priority Queue has" << endl;
   myqueue.insert(34);
   cout << endl << endl;

  
   cout << "After inserting 63 Priority Queue has" << endl;
   myqueue.insert(63);
   cout << endl << endl;

  
   cout << "After extracting the minimum value Priority Queue has" << endl;
   myqueue.extractMin();
   cout << endl << endl;

  
   cout << "After inserting 75 Priority Queue has" << endl;
   myqueue.insert(75);
   cout << endl << endl;

  
   cout << "After inserting 85 Priority Queue has" << endl;
   myqueue.insert(85);
   cout << endl << endl;

  
   cout << "After extracting the minimum value Priority Queue has" << endl;
   myqueue.extractMin();
   cout << endl << endl;

   cout << "Minimum value is ";
   cout << myqueue.min() << endl << endl; //prints out heap min

   system("pause");
   return 0;
}

//source

#include <iostream>
using namespace std;
#include "header.h"

priorityQueue::priorityQueue() //constructor
{
   int size = 0;
   data = new int[size];
}

priorityQueue::~priorityQueue() //destructor
{

}

int priorityQueue::getParent(int index) //finds parent
{
   return (index - 1) / 2;
}

int priorityQueue::getLeftChild(int index) //finds left child
{
   return (2 * index) + 1;
}

int priorityQueue::getRightChild(int index) //find right child
{
   return (2 * index) + 2;
}

void priorityQueue::swap(int& item1, int& item2) //swaps value of two variables
{

   int temp = item1;
   item1 = item2;
   item2 = temp;
}

//void priorityQueue::heapify(int index) //heapifies the heap
//{
//   int small = index;
//   int l = getLeftChild(index);
//   int r = getRightChild(index);
//  
//   if (l < size && data[l] < data[index])
//   {
//       small = l;
//   }
//   else
//   {
//       small = index;
//   }
//}

void priorityQueue::heapify(int index) //heapifies the heap
{
   int small = index;
   int l = getLeftChild(index);
   int r = getRightChild(index);

   if (l <= data[size] && data[l] < data[index])
   {
       small = l;
   }
   else
   {
       small = index;
   }
   if (r <= data[size] && data[r] < data[small])
   {
       small = r;
   }

   if (small != index)
   {
       swap(data[index], data[small]);
       heapify(small);
   }

}

void priorityQueue::printArray(int []) //prints array
{
  
   for (int i = 0; i < size; i++)
   {
       cout << data[i] << ", ";
   }

  
}

int priorityQueue::extractMin() //finds min and removes it
{
   int min = data[0];
   data[0] = data[size];
   size = size - 1;
   heapify(data[size]);
   return min;
  
}

int priorityQueue::min() const // finds min
{
   return data[0];
}

bool priorityQueue::empty() const // checks if heap is empty
{
   if (data != NULL)
   {
       cout << "My priority Queue is empty " << endl << endl;
       return false;
   }
   else
   {
      
       return true;
      
   }
}

void priorityQueue::insert(int Item) //inserts values into heap
{
   size += 1;
   int i = size - 1;
   while (i > 0 && data[getParent(i)] > Item)
   {
       data[i] = data[getParent(i)];
       i = getParent(i);
   }
   data[i] = Item;

   printArray(data);
}

//This is my output

//This is suppose to me my output. I thnik there is something wrong with my extractmin.

E#ifndef PRIORITYQUEUE #define PRIORITYQUEUE #include kiostream Eclass priority Queue private: int size; int data public: static const int CAPACITY 50 priority ();//constructor //destructor priority Queue int getParent(int index); int get Leftchild(int index); int getRightChild(int index) void swap (int &, int &) void insert (int item) //enqueue heap insert void print Array(int [J); void heapify (int index); //remove and return the smallest item currently in the priority queue int extractMin();//dequeue bool empty() const int min const; //return the smallest item #endif

Explanation / Answer

Please let me in case of any issue.

Hi, there is error in extractMin() function.
Instead of data[0] = data[size]; this should be data[0] = data[size-1];

int priorityQueue::extractMin() //finds min and removes it
{
int min = data[0];
data[0] = data[size];
size = size - 1;
heapify(data[size]);
return min;
  
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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