C++: Using a heap, implement the priority queue class. The class should have a s

Question

C++: Using a heap, implement the priority queue class. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap and an array,data, that contains the heap with the entries. We also want to have FIFO behavior for entries with the equal priority. To obtain this behavior, the class should have an extra extra private member variable that is an array, order, where order[i] contains the order in which data [i] was added to the queue. For example, if entry[7] was 33rd item added to the priority queue, then order [7] would be 33. When you are comparing two entries with equal priority, use the order number to "break the tie"(so that if two entries have the same priority number,then the one with the earlier order number will come out of th priority queue first).


Template<class item > Class simple_priority_queue { Public: Typedef Item value_type; Typedef std::size_t size_type; Static const size_type CAPACITY=50; Priority_queue(); Void pop(); Void push(const Item& entry ); bool empty() const; Size_type size() const; Item top()const;
Private: Item data [CAPACITY]; Size_type used; }; C++: Using a heap, implement the priority queue class. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap and an array,data, that contains the heap with the entries. We also want to have FIFO behavior for entries with the equal priority. To obtain this behavior, the class should have an extra extra private member variable that is an array, order, where order[i] contains the order in which data [i] was added to the queue. For example, if entry[7] was 33rd item added to the priority queue, then order [7] would be 33. When you are comparing two entries with equal priority, use the order number to "break the tie"(so that if two entries have the same priority number,then the one with the earlier order number will come out of th priority queue first).


Template<class item > Class simple_priority_queue { Public: Typedef Item value_type; Typedef std::size_t size_type; Static const size_type CAPACITY=50; Priority_queue(); Void pop(); Void push(const Item& entry ); bool empty() const; Size_type size() const; Item top()const;
Private: Item data [CAPACITY]; Size_type used; };


Template<class item > Class simple_priority_queue { Public: Typedef Item value_type; Typedef std::size_t size_type; Static const size_type CAPACITY=50; Priority_queue(); Void pop(); Void push(const Item& entry ); bool empty() const; Size_type size() const; Item top()const;
Private: Item data [CAPACITY]; Size_type used; };

Explanation / Answer

#include <assert.h> // Provides assert function
#include <iomanip> // Provides setw
#include <iostream> // Provides cin, cout
#include <math.h> // Provides log2
#include "pqueue2.h"

using namespace std;

PriorityQueue::PriorityQueue( )
{
heap[CAPACITY];
many_items=0;
}

void PriorityQueue::insert(const Item& entry, unsigned int priority)
{
if(many_items==0)
{
heap[many_items].data= entry;
heap[many_items].priority= priority;
many_items++;
}
else
{
heap[many_items].data= entry;
heap[many_items].priority= priority;
unsigned int i= many_items;
many_items++;
while(parent_priority(i)<priority)
{
swap_with_parent(i);
i=parent_index(i);
}
}
}

PriorityQueue::Item PriorityQueue::get_front( )
{
assert(many_items>0);
if(many_items==1)
{
Item front_value=heap[0].data;
many_items--;
return front_value;
}
else
{
Item front_value=heap[0].data;
heap[0]=heap[many_items-1];
unsigned int priority= heap[many_items-1].priority;
unsigned int k=0;
while( (k<many_items) && !is_leaf(k) && big_child_priority(k)>priority)
{
unsigned int j=big_child_index(k);
swap_with_parent(big_child_index(k));
k= j;
}
many_items--;
return front_value;
}
}

bool PriorityQueue::is_leaf(size_t i) const
{
if(((2*i)+1)>=many_items)
return 1;
else
return 0;
}

size_t PriorityQueue::parent_index(size_t i) const
{

return (i-1)/2;
}

unsigned int PriorityQueue::parent_priority(size_t i) const
//return highest priority heap[i].
{
return heap[ (i-1)/2].priority;
}

size_t PriorityQueue::big_child_index(size_t i) const
// return highest priority. child
{
assert(!is_leaf(i));
if((2*i)+2<many_items)
{
if(heap[(2*i)+1].priority>heap[(2*i)+2].priority)
{
return (2*i)+1;
}
else
{
return (2*i)+2;
}
}
else
{
return(2*i)+1;
}
}

unsigned int PriorityQueue::big_child_priority(size_t i) const
{
return heap[big_child_index(i)].priority;
}

void PriorityQueue::swap_with_parent(size_t i)
{
assert( i>0 && i<many_items);
OneItemInfo temp_parent=heap[parent_index(i)];
OneItemInfo temp_child=heap[i];
heap[i]=temp_parent;
heap[parent_index(i)]=temp_child;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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