Implement a Priority Queue ADT with efficient Enqueue and Dequeue operations (and only these two) using a max heap to store queue items. A max heap is a complete binary tree, implemented using an array, where the value of a parent node is always larger than (or equal to) the values of its child nodes.

Enqueue means to insert a new item into the max heap. The steps are as follows:

- add the new item/node at the end of the heap array;

- set node to last node;

- while the node's value is larger than the parent's value:

- swap node and parent values;

- go to parent;

- increase the heap size by 1.

Dequeue means to delete and return the root item from the max heap. The steps are:

- save the root item and return it at the end;

- replace the root item with the last item/node in the heap array;

- set node to root;

- while the node has 1 or 2 child nodes:

- set next-node to the child node with the largest value;

- if the node value is smaller than the next node value:

- swap the values;

- go to next node;

- decrease the heap size by 1.

Make sure to use recursion to implement both Enqueue and Dequeue operations (and not loops!) and to test your code.

PriorityQueue.h

/*

Define the queue class that uses array structure

*/

#ifndef q_h

#define q_h

//#include "ItemType.h"

#include

using namespace std;

const int MAX_ITEMS = 10;

typedef int ItemType ;

enum Error_code {Success, Overflow, Underflow};

class PQueueType

{

public:

PQueueType( int max = MAX_ITEMS);//PARAMETERIZED CONSTRUCTOR

bool IsFull( ) const;

bool IsEmpty( ) const;

Error_code Enqueue(ItemType item);

Error_code Dequeue( ItemType& item );

void printPQueueItems(ostream & out);

private:

int count;

int maxQueue;

ItemType* items; // DYNAMIC ARRAY IMPLEMENTATION

void upHeap(int root, int bottom);

void downHeap(int root, int bottom);

};

#endif

Appendix:

A heap is binary tree that satisfies two properties

-Binary tree meets the shape property(Binary tree is complete)

-Binary tree meets the order property(For a max heap, for every node in the in the heap, the value stored in that node is greater than or equal to the value in each of its children and in min heap for every node in the in the heap, the value stored in that node is less than or equal to the value in each of its children)

An example of max heap:

Insert operation (Enqueue operation in PriorityQueue that uses max heap)

As an example of binary heap insertion, say we have a max heap

and we want to add the number 15 to the heap. We first place the 15 in the position marked by the X. However, the heap property is violated since 15 > 8, so we need to swap the 15 and the 8. So, we have the heap looking as follows after the first swap:

However the heap property is still violated since 15 > 11, so we need to swap again:

which is a valid max heap. There is no need to check the left child after this final step: at the start, the max heap was valid, meaning 11 > 5; if 15 > 11, and 11 > 5, then 15 > 5, because of the transitive relation.

Delete operation (Dequeue operation in PriorityQueue that uses max heap)

The procedure for deleting the root from the heap (effectively extracting the maximum element in a max heap and restoring the order property properties is called down-heap. The steps are:

Replace the root of the heap with the last element on the last level.

Compare the new root with its children; if they are in the correct order, stop.

If not, swap the element with one of its children that has max value and return to the previous step.

So, if we have the same max heap as before

We remove the 11 and replace it with the 4.

Now the heap property is violated since 8 is greater than 4. In this case, swapping the two elements, 4 and 8, is enough to restore the heap property and we need not swap elements further: