Goal is to do Problem 2. IN C++ 1) Using a heap, implement the priority queue. T

Question

Goal is to do Problem 2.

IN C++

1) Using a heap, implement the priority queue. 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 equal priority. TO obtain this behavior the class should have an extra private member variable that is an array, order, where order [ i ] contains the order in which data[ i ] was added to the queue. As an example, if entry [ 7 ] was the 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 the priority queue first)

2). Implement problem 1 with NO PREDIFINED LIMIT ON THE SIZE OF THE HEAP USING A VECTOR

* Use the heap class to implement a priority queue *

----- Use the following header files ------

heap.h

#ifndef _HEAP_H_
#define _HEAP_H_

#include
#include

// This class implements an unbounded max heap.

// class invariant: heap property is satisfied for a max heap

template
class heap
{
public:
heap();
// postcondition: empty heap has been created
unsigned int size() const;
// postcondition: number of elements in a heap has been returned
bool is_empty() const;
// postcondtion: returned whether the heap is empty
void insert (const T& item);
// postcondition: item has been added
void remove();
// precondition: heap is not empty
// postcondition: largest item has been removed from the heap
T max() const;
// precondition: heap is not empty
// postcondition: copy of largest element in the heap has been returned
T& max();
// precondition: heap is not empty
// postcondition: access to largest element in the heap has been returned
private:
std::vector v;
unsigned int max_child (unsigned int index) const;
// precondition: element at index has children
// postcondition: index of the larger child has been returned
// if there is only 1 child - index of that child has been returned
};

#include "heap.template"

#endif // _HEAP_H_

priority_queue.h

#ifndef _PRIORITY_QUEUE_H
#define _PRIORITY_QUEUE_H

#include "heap.h"

template
class priority_queue
{
public:
priority_queue();
// postcondition: empty priority_queue has been created
void pop();
// precondition: priority_queue is not emtpy
// postcondition: highest priority item has been removed
void push (const T& item);
// postcondition: item has been inserted
bool empty () const;
// postcondition: returned whether priority queue is empty
unsigned int size() const;
// postcondition: returned number of items in the priority queue
T top() const;
// precondition: priority queue is not empty
// postcondition: copy of highest priority item has been returned
private:
heap h;
};

#include "priority_queue.template"

#endif // _PRIORITY_QUEUE_H

Explanation / Answer

#include<stdio.h>
#include<conio.h>
#define max 100
void insert();
void deletee();
void display();
int qu[max];
int front=0,rear=-1;
void main()
{
int choice;
char ch;
do
{
   printf("Enter your option ");
   printf("1 . insert ");
   printf("2 . deleation ");
   printf("3 . display ");
   scanf("%d",&choice);
   switch(choice)
       {
   case 1: insert();
       break;
   case 2: deletee();
       break;
   case 3:display();
       break;
   default:printf("You entered wrong choice");
   }
   printf(" Do you wish to continue");
   fflush(stdin);
   scanf("%c",&ch);
}
   while(ch=='y' || ch=='Y');
}

void deletee()
{
int item;
int i;
if(front<0)
{
   printf("queue is empty");
   getch();
   exit();
}
   else
   {
   item=qu[front];
   front=front+1;
   printf("Delete element is %d",item);
   }
}

void insert()
{
int item;
if(rear>=max)
{
   printf("queue is full");
   getch();
   exit(0);
}
   else
   {
   printf("Element to insert ");
   scanf("%d",&item);
   rear=rear+1;
   qu[rear]=item;
   printf(" insert is success ");
   }
}
void display()
{
int i;
for(i=front;i<=rear;i++)
{
printf("%d ",qu[i]);
}

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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