C++ Question
Can I get an example of a max heap that has an insert function, delete function and a print function?
Please use namespace std and iostream and whatever else is needed I guess.
`Hey,
Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries
#include <iostream>
#include<vector>
using namespace std;
// Data structure for Max Heap
struct PriorityQueue
{
private:
// vector to store heap elements
vector<int> A;
// return parent of A[i]
// don't call this function if it is already a root
node
int PARENT(int i)
{
return (i - 1) / 2;
}
// return left child of A[i]
int LEFT(int i)
{
return (2 * i + 1);
}
// return right child of A[i]
int RIGHT(int i)
{
return (2 * i + 2);
}
// Recursive Heapify-down algorithm
// the node at index i and its two direct
children
// violates the heap property
void heapify_down(int i)
{
// get left and right child of node
at index i
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
// compare A[i] with its left
and right child
// and find largest value
if (left < size() &&
A[left] > A[i])
largest =
left;
if (right < size() &&
A[right] > A[largest])
largest =
right;
// swap with child having
greater value and
// call heapify-down on the
child
if (largest != i) {
swap(A[i],
A[largest]);
heapify_down(largest);
}
}
// Recursive Heapify-up algorithm
void heapify_up(int i)
{
// check if node at index i and its
parent violates
// the heap property
if (i && A[PARENT(i)] <
A[i])
{
// swap the two
if heap property is violated
swap(A[i],
A[PARENT(i)]);
// call
Heapify-up on the parent
heapify_up(PARENT(i));
}
}
public:
// return size of the heap
unsigned int size()
{
return A.size();
}
// function to check if heap is empty or not
bool empty()
{
return size() == 0;
}
// insert key into the heap
void insert(int key)
{
// insert the new element to the
end of the vector
A.push_back(key);
// get element index and call
heapify-up procedure
int index = size() - 1;
heapify_up(index);
}
// function to remove element with highest priority
(present at root)
void deletes()
{
// if heap
has no elements, throw an exception
if (size() ==
0)
{
cout<<"Can't delete empty heap\n";
return;
}
// replace
the root of the heap with the last element
// of the
vector
A[0] =
A.back();
A.pop_back();
// call
heapify-down on root node
heapify_down(0);
}
// function to return element with highest priority
(present at root)
int top()
{
// if heap
has no elements, throw an exception
if (size() ==
0)
{
cout<<"Can't return empty heap\n";
return -1;
}
// else
return the top (first) element
return
A.at(0); // or return A[0];
// catch and print the exception
}
};
int main()
{
PriorityQueue pq;
// Note - Priority is decided by element's value
pq.insert(3);
pq.insert(2);
pq.insert(15);
cout << "Size is " << pq.size() << endl;
cout << pq.top() << " ";
pq.deletes();
cout << pq.top() << " ";
pq.deletes();
pq.insert(5);
pq.insert(4);
pq.insert(45);
cout << endl << "Size is " << pq.size() << endl;
cout << pq.top() << " ";
pq.deletes();
cout << pq.top() << " ";
pq.deletes();
cout << pq.top() << " ";
pq.deletes();
cout << pq.top() << " ";
pq.deletes();
cout << endl << std::boolalpha << pq.empty();
return 0;
}
Kindly revert for any queries
Thanks.
C++ Question Can I get an example of a max heap that has an insert function,...
please solve this question: Write a character Max-Heap Builder program in C++. The program should display the menu below. Each item in the menu should be implemented in a function. a. Add a node. One node to be added to the max-heap. b. Delete a node. One node to be deleted from the max-heap. C. Search a node. Returns true if the node exists in the max-heap, otherwise it returns false. d. Print the tree. Prints the heap in level-order...
Using C++, data structures, C++ STL, inputs and expected outputs are shown below. Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it...
Write a C program insertion and deletion functions for a max heap represented as a linked binary tree. Assume that each node has a parent field as well as the usual left child, right child, and key fields. -Condition : Do not use Array representation. Use the following structure. typedef struct node *treePointer; typedef struct node { int key; treePointer parent; treePointer leftChild, rightChild; }; - INPUT i k : Insert the node with the key value of k in...
Write a C program insertion and deletion functions for a max heap represented as a linked binary tree. Assume that each node has a parent field as well as the usual left child, right child, and key fields. -Condition : Do not use Array representation. Use the following structure. typedef struct node *treePointer; typedef struct node { int key; treePointer parent; treePointer leftChild, rightChild; }; - INPUT i k : Insert the node with the key value of k in...
Write a program in Java to implement the max-priority queue using max-heap data structure. Implement the max-heap data structure using an integer array of 10 cells. (Do not use Java in-built PriorityQueue class.) [In a max-heap, the root node and the intermediate node vales are always greater than their children.] First, take 10 integer values from the user and insert them in the max-priority queue. Then print the elements of the queue. After that, delete two elements from the queue...
Task: A ternary heap is like a binary heap, except instead of each node having a max of two children, each node has a max of three children. Given a ternary min heap, return true if it is a valid heap. That is, it satisfies the heap property (the parent is less than all of its children) Requirements: Implement an isValidHeap function to determine whether a particular array of integers constitutes a valid ternary min-heap. bool isValidHeap(int arr[])// example declaration...
C++: what is i and j. IMPORTANT I know it's 3 and 3 but can someone please explain how we can get to that conclusion by just reading the code, can it be explained to me because when i try to do it I get a different answer for i and j I got 1 and 4. #include <iostream> using namespace std; int main() { int i = 1; int j = 0; if (i++ == 1) { j =...
The question I want answered is in C++. How can I pass a value to a function and create a new linked list out of it? For example I have: void getIntegerInput(List<int> list) { int s; std::cout << "Type a positive integer then click enter to add it to the linked list\n"; std::cout << "Type -1 to stop\nType -2 to delete an item from the list\n"; std::cin >> s; while (s != -1) { if (s == -2) { int...
PROGRAM DESCRIPTION Using the given class definitions for either C++, create a minimum heap that stores integers and and implements a minimum priority queue. (Your program can be "hard coded" for integers - it does not need to use templates, generics, or polymorphism.) Your data structure must always store its internal data as a heap. Your toString function should return a string with the heap values as a comma separated list, also including the size of the heap as well....