Build a Double-Ended Priority Queue with insert, min, max, pop_min, and pop_max.

Question

Build a Double-Ended Priority Queue with insert, min, max, pop_min, and pop_max. Build it by having two heaps (one min-heap and one max-heap), but the array should be an array of Nodes. Where each Node stores data and the index of the partner value in the other heap.

#include using namespace std; int main() { //Create a class called DEPQ which implements // (at least) three methods: // void DEPQ::insert(n) // int DEPQ::pop_max(); // int DEPQ::pop_min(); // All three operations should take O(log(n)) time DEPQ dePQ; dePQ.insert(11); dePQ.insert(3); dePQ.insert(7); dePQ.insert(13); dePQ.insert(2); dePQ.insert(17); dePQ.insert(5); dePQ.insert(19); //We should see the commented values in that order cout << dePQ.pop_min() << endl; //2 cout << dePQ.pop_max() << endl; //19 cout << dePQ.pop_min() << endl; //3 cout << dePQ.pop_max() << endl; //17 cout << dePQ.pop_min() << endl; //5 cout << dePQ.pop_max() << endl; //13 cout << dePQ.pop_min() << endl; //7 cout << dePQ.pop_max() << endl; //11 }

Explanation / Answer

#include <iostream>
using namespace std;

#define MAX_ELEMENTS 100

//structure of a node in priority queue
typedef struct {
   int data;
   int partner;
} NODE;

//class definition for double-ended priority queue
class DEPQ {
private:
   NODE minheap[MAX_ELEMENTS];
   NODE maxheap[MAX_ELEMENTS];
   int num_elements;
   bool is_empty();
   void swap_minheap(int, int); //swaps two nodes in minheap
   void swap_maxheap(int, int); //swaps two nodes in maxheap
   int insert_minheap(NODE&); //returns the position at which node is inserted in minheap
   int insert_maxheap(NODE&); //returns the position at which node is inserted in maxheap
   void delete_minheap(int); //deletes a node from minheap partner to a node in maxheap
   void delete_maxheap(int); //deletes a node from maxheap partner to a node in minheap

public:
   DEPQ() :
           minheap { }, maxheap { } {
       num_elements = 0;
   }
   int size();
   int min();
   int max();
   void insert(int);
   int pop_max();
   int pop_min();
};

//Implementation of private methods
bool DEPQ::is_empty() {
   return (num_elements == 0);
}

void DEPQ::swap_minheap(int pos1, int pos2) {
   NODE temp;
   //cout << pos1 << " " << pos2 << endl;
   temp = minheap[pos1];
   //cout << "temp:" << temp.data << endl;

   minheap[pos1] = minheap[pos2];
   //cout << "temp1:" << minheap[pos2].data << endl;

   minheap[pos2] = temp;
   //cout << "temp2:" << minheap[pos2].data << endl;

}

void DEPQ::swap_maxheap(int pos1, int pos2) {
   NODE temp;
   temp = maxheap[pos1];
   maxheap[pos1] = maxheap[pos2];
   maxheap[pos2] = temp;
}

int DEPQ::insert_minheap(NODE& node) {
   /*if(size()==MAX_ELEMENTS)
   {
   cerr<<"Overflow!!!"<<endl;
   return -1;
   }*/
   //num_elements++;
   int node_position = num_elements - 1;
   int parent_node_position = (node_position - 1) / 2;
   minheap[node_position] = node; //insert node at end of minheap.
   while (node_position != 0
           && (minheap[node_position].data < minheap[parent_node_position].data)) {
       swap_minheap(node_position, parent_node_position);
       node_position = parent_node_position;
       parent_node_position = (node_position - 1) / 2;
   }
   return node_position;
}

int DEPQ::insert_maxheap(NODE& node) {
   /*if(size()==MAX_ELEMENTS)
   {
   cerr<<"Overflow!!!"<<endl;
   return -1;
   }*/
   //num_elements++;
   int node_position = num_elements - 1;
   int parent_node_position = (node_position - 1) / 2;
   maxheap[node_position] = node; //insert node at end of maxheap.
   while (node_position != 0
           && (maxheap[node_position].data > maxheap[parent_node_position].data)) {
       swap_maxheap(node_position, parent_node_position);
       node_position = parent_node_position;
       parent_node_position = (node_position - 1) / 2;
   }
   return node_position;
}

void DEPQ::delete_minheap(int pos) {
   int node_position = pos;
   //NODE node_to_be_removed=minheap[node_position];
   //int data_to_be_removed=node_to_be_removed.data;
   int last_node_position = num_elements - 1;
   swap_minheap(node_position, last_node_position);
   while (node_position < num_elements) {
       int left_child_position = 2 * node_position + 1;
       int right_child_position = 2 * node_position + 2;
       if (left_child_position < num_elements
               && right_child_position < num_elements) {
           int node_data = minheap[node_position].data;
           int left_child_data = minheap[left_child_position].data;
           int right_child_data = minheap[right_child_position].data;
           if (node_data > left_child_data || node_data > right_child_data) {
               int position_to_swap;
               if (left_child_data < right_child_data) {
                   position_to_swap = left_child_position;
               } else if (right_child_data < left_child_data) {
                   position_to_swap = right_child_position;
               }
               swap_minheap(node_position, position_to_swap);
               node_position = position_to_swap;
           }
       }
   }
}

void DEPQ::delete_maxheap(int pos) {
   int node_position = pos;
   //NODE node_to_be_removed=maxheap[node_position];
   //int data_to_be_removed=node_to_be_removed.data;
   int last_node_position = num_elements - 1;
   swap_maxheap(node_position, last_node_position);
   while (node_position < num_elements) {
       int left_child_position = 2 * node_position + 1;
       int right_child_position = 2 * node_position + 2;
       if (left_child_position < num_elements
               && right_child_position < num_elements) {
           int node_data = maxheap[node_position].data;
           int left_child_data = maxheap[left_child_position].data;
           int right_child_data = maxheap[right_child_position].data;
           if (node_data > left_child_data || node_data > right_child_data) {
               int position_to_swap;
               if (left_child_data < right_child_data) {
                   position_to_swap = left_child_position;
               } else if (right_child_data < left_child_data) {
                   position_to_swap = right_child_position;
               }
               swap_maxheap(node_position, position_to_swap);
               node_position = position_to_swap;
           }
       }
   }
}

//Implementation of public methods
int DEPQ::size() {
   return num_elements;
}

//return minimum element in DEPQ
int DEPQ::min() {
   return minheap[0].data;
}

//return maximum element in DEPQ
int DEPQ::max() {
   return maxheap[0].data;
}

//inserts a given value in DEPQ
void DEPQ::insert(int n) {
   if (size() == MAX_ELEMENTS) {
       cerr << "Overflow!!!" << endl;
       return;
   }
   NODE minheap_node, maxheap_node;
   num_elements++;
   minheap_node.data = n;
   maxheap_node.data = n;
   int minheap_node_position = insert_minheap(minheap_node);
   int maxheap_node_position = insert_maxheap(maxheap_node);
   minheap_node.partner = maxheap_node_position;
   maxheap_node.partner = minheap_node_position;
}

int DEPQ::pop_max() {
   if (is_empty()) {
       cerr << "Underflow!!!" << endl;
       return -1;
   }
   int max;
   int max_node_position = 0;
   NODE max_node = maxheap[max_node_position];
   max = max_node.data;
   int partner_minheap = max_node.partner;
   int last_node_position = num_elements - 1;
   swap_maxheap(max_node_position, last_node_position);
   num_elements--;

   while (max_node_position < num_elements) {
       int max_node_data = maxheap[max_node_position].data;
       int position_to_swap;
       int left_child_position = 2 * max_node_position + 1;
       int right_child_position = 2 * max_node_position + 2;

       if (right_child_position >= num_elements) {
           if (right_child_position >= num_elements) {
               break;
           } else {
               position_to_swap = left_child_position;
           }
       } else {
           int left_child_data = maxheap[left_child_position].data;
           int right_child_data = maxheap[right_child_position].data;
           if (left_child_data > right_child_data) {
               position_to_swap = left_child_position;
           } else {
               position_to_swap = right_child_position;
           }
       }
       if (max_node_data < maxheap[position_to_swap].data) {
           swap_maxheap(max_node_position, position_to_swap);
           max_node_position = position_to_swap;
           //       cout << "min pos:" << min_node_position << endl;
       }
   }

   //delete_minheap(partner_minheap);
   return max;
}

int DEPQ::pop_min() {
   if (is_empty()) {
       cerr << "Underflow!!!" << endl;
       return -1;
   }
   int min;
   int min_node_position = 0;
   NODE min_node = minheap[min_node_position];
   min = min_node.data;
   //cout << "min:" << min << endl;
   int partner_maxheap = min_node.partner;
   int last_node_position = num_elements - 1;
   //cout << "last node position:" << last_node_position << endl;
   swap_minheap(min_node_position, last_node_position);
   //cout << "swapped last value:" << minheap[min_node_position].data << endl;
   num_elements--;
   while (min_node_position < num_elements) {
//cout<<"Rearranging..."<<endl;
       int left_child_position = 2 * min_node_position + 1;
       int right_child_position = 2 * min_node_position + 2;
       int min_node_data = minheap[min_node_position].data;
       int position_to_swap;
       if (right_child_position >= num_elements) {
           if (right_child_position >= num_elements) {
               break;
           } else {
               position_to_swap = left_child_position;
           }
       } else {
           int left_child_data = minheap[left_child_position].data;
           int right_child_data = minheap[right_child_position].data;
           if (left_child_data < right_child_data) {
               position_to_swap = left_child_position;
           } else {
               position_to_swap = right_child_position;
           }
       }
//cout<<"Rearranging..."<<endl;

       if (min_node_data > minheap[position_to_swap].data) {
           swap_minheap(min_node_position, position_to_swap);
           min_node_position = position_to_swap;
           //       cout << "min pos:" << min_node_position << endl;
       }
   }

//delete_maxheap (partner_maxheap);
   return min;
}

int main() {
//Create a class called DEPQ which implements
// (at least) three methods:
// void DEPQ::insert(n)
// int DEPQ::pop_max();
// int DEPQ::pop_min();
// All three operations should take O(log(n)) time
   DEPQ dePQ;
   cout << "Inserting in DEPQ..." << endl;
   dePQ.insert(11);
   dePQ.insert(3);
   dePQ.insert(7);
   dePQ.insert(13);
   dePQ.insert(2);
   dePQ.insert(17);
   dePQ.insert(5);
   dePQ.insert(19);
   cout << "Inserting complete!" << endl;
   cout << "size:" << dePQ.size() << endl;
   cout << "Max:" << dePQ.max() << endl;
   cout << "Min:" << dePQ.min() << endl;

//We should see the commented values in that order.
   cout << dePQ.pop_min() << endl;   //2
   cout << dePQ.pop_max() << endl;   //19
//cout << dePQ.pop_min() << endl;
//3 cout << dePQ.pop_max() << endl;
//17 cout << dePQ.pop_min() << endl;
//5 cout << dePQ.pop_max() << endl;
//13 cout << dePQ.pop_min() << endl;
//7 cout << dePQ.pop_max() << endl;
//11 }
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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