Need help with a C++ program invoving heaps Please follow the images below. ntro

ID: 3811267 • Letter: N

Question

Need help with a C++ program invoving heaps

Please follow the images below.

ntroduction Heaps are commonly referred to as priority queues. The reason is because all elements in the heap are organized relative to a given heap order property. This property requires that items retrieved from the heap is either the smallest value in the heap (called a min heap), or the largest value in the heap called a max heap). In other words, when retrieving data from a min heap, the element with the smallest value over all elements in the heap has priority and is removed first; the same holds for a max heap. The heap data structure is a complete binary tree, implemented as a static or dynamic array, where each subtree i he tree also follow the heap order property (i.e. the root is either the minimal or maximal value in that subtree) Objective To gain experience implementing a heap using an array based binary tree, learn how use the STL vector container, learn how to sort values using heap sort. operations performed upon the heap Since the heap is implemented as an array-based complete binary tree, traversing the tree can be done by simply calculating the index of the next node (or element) to traverse to (or move). How the tree i indexed has been discussed in lecture and is also provided in your text book and the tree lecture slides. Most of the heap operations function were discussed class (and slides) so the below paragraphs will rovide a brief overview: it is assumed that you were present and paid attention in class enqueue: Adds/inserts an item to the heap. An item added to the heap is positioned as the last element of the array at location heapsize 1, where heapsize is the number of elements in the array It the performs the bubble-up operation on that new item. During bubble-up, the newly added item is checked to see if it, at its current position, meets the heap order property when compared to its parent. If it does not, the bubble-up operation moves the new item up the tree until it is in a position that meets the heap order property. Bubble-up can be done iterative or recursively dequeue: Removes/Deletes an item from the heap. Deletions from the heap removes the root from the tree where the root is the first element in the arra the element is either element zero or one depending y, on how the array is indexed. After removing the root, the last element in the heap is moved (i.e., a simple assignment operation) to the array location of the former root and then the bubble-down operation ISS performed on the "new root". The bubble-down operation checks if the "new root" meets the heap order property by comparing it with the value of its children. If it does not, bubble-do wi move the "new root" down the tree until it is in a position that meets the heap order property. Otherwise, if the "new root" meets the heap-order property, bubble-down isn't performed build heap: Builds a heap from a populated array. Build heap is an iterative process that starts at the size/2l, assuming root is at 1) and iterates up to the root center of the tree (the node at index node. At each iteration (i de), it executes the bubble do process starting at the array element of its current position nstructions Your assignment is to write a dynamic array-based Heap class. Your Heap class will support both a min heap structure and a max-heap structure, specified by passing a Boolean argument to the constructor at the creation of a Heap object. Since this is an array-based heap, the "node data" is the priority. You are to implement three operations described above and all other methods specified in the below UML.

Explanation / Answer

Here we are writing code for C++ program involving heaps

Part-1

Part-2

Now, main.cpp

#include <iostream>

#include <string>

#include "Heap.h"

using std::cout;

using std::endl;

typedef int TYPE;

int main(void) {

Heap<TYPE> *heap = new Heap<TYPE>(); // numeric type heap

TYPE item = 0;

Heap<std::string> *s_heap = new Heap<std::string>(); // string heap

std::string s_item = "y";

std::vector<std::string> s_blah(11,s_item);

cout << "*** Test insert elements ***";

heap->Insert(15);

heap->Insert(1);

heap->Insert(3);

heap->Insert(4);

heap->print_heap(); //should print 15 4 3 1 and it does

cout << endl;

cout << " *** Test delete elements *** "; //delete also works fine 15, 4, 3, 1 and then returns 0

cout << item << " " << heap->Delete(item) << endl;

cout << "the next delete should return false (i.e. 0) ";

cout << item << " " << heap->Delete(item) << endl;

cout << " *** Test Heap(vector,bool) *** ";

std::vector<TYPE> blah(11, 99);

blah[1] = 15;

blah[2] = 4;

blah[3] = 12;

blah[4] = 3;

blah[5] = 22;

blah[6] = 37;

blah[7] = 9;

blah[8] = 1;

blah[9] = 7;

blah[10] = 3;

delete heap;

heap = new Heap<TYPE>(blah, false); // false make it a min heap

heap->print_heap();

//here it prints wrong> 99 15 4 12 3 22 37 9 1 7 3

//and it should print> 1 3 4 9 3 22 37 15 12 7 99

cout << endl;

// Sting heap test

cout << " *** Test insert elements ***";

s_heap->Insert("15");

s_heap->Insert("11");

s_heap->Insert("13");

s_heap->Insert("43");

cout << endl;

s_heap->print_heap();

//works fine, prints out 43, 15, 13, 11

cout << " *** Test delete elements *** ";

cout << s_item << " " << s_heap->Delete(s_item) << endl;

cout << "the next delete should return false (i.e. 0) ";

cout << s_item << " " << s_heap->Delete(s_item) << endl;

//deletes fine

cout << " *** Test Heap(vector,bool) *** ";

s_blah[1] = "a";//"15";

s_blah[2] = "c";//"4";

s_blah[3] = "e";//"12";

s_blah[4] = "d";//"3";

s_blah[5] = "f";//"22";

s_blah[6] = "h";//"37";

s_blah[7] = "s";//"9";

s_blah[8] = "b";//"1";

s_blah[9] = "v";//"7";

s_blah[10] = "z";//"3";

delete s_heap;

s_heap = new Heap<std::string>(s_blah, false);

s_heap->print_heap();

cout << endl;

//again, messes up here> it prints:

//z y c e a f h s b v d

//it should print>

a b c e d f h s y v z

cout << "*** Emptying heap *** ";

unsigned int size = s_heap->size();

for(unsigned int i=0; i<size; i++) {

s_heap->Delete(s_item);

cout << s_item << " ";

}

cout << " ********************* ";

cout << endl;

} // end to main

Navigate

Need help with a C++ assignment I have three files main.cpp, time.cpp and time.h

Need help with a C++ program invoving heaps along with the analysis questions nt

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

Need help with a C++ program invoving heaps Please follow the images below. ntro

Question

Explanation / Answer

Related Questions

Navigate