A Max Heap data structure is a complete binary tree, implemented using an array

Question

A Max Heap data structure 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. It can be used for instance to implement priority queues with efficient enqueue/dequeue operations.

Enqueue i.e., inserting a new item into the max heap, works as follows:

- add the new item/node at the end of the heap array(as last item/node of the array);

- set node to last node;

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

        - swap the values;

        - go to parent;

- increase heap size by 1;

Dequeue i.e., removing the root item from the max heap, works as follows:

-dequeue the item at the root node;

-copy the last value in the heap array to the root;

-decrease the heap size by 1;

-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

Implement a PriorityQueue ADT with its Enqueue and Dequeue operations, as described above. Make sure to use recursion in Enqueue and Dequeue operations and not loops. Test it . . .

Note: Find more explanation of max heap and Enqueue and Dequeue operations on PriorityQueue in the appendix section.

use c++ and data stricture

Explanation / Answer

/*

* C++ Program to Implement Priority Queue to Add and Delete Elements

*/

#include <stdio.h>

          #include <stdlib.h>

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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