1) Heap Operation This question is designed to help you get a better understandi
ID: 3607600 • Letter: 1
Question
1) Heap Operation
This question is designed to help you get a better understanding of basic heap operations.
You will be given queries of types:
"1 v " - Add an element to the heap.
"2 v " - Delete the element from the heap.
"3" - Print the minimum of all the elements in the heap.
NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.
Input Format
The first line contains the number of queries, Q .
Each of the next Q lines contains a single query of any one of the above mentioned types.
Output Format
For each query of type 3, print the minimum value on a single line.
Explanation
After the first 2 queries, the heap contains {4,9}. Printing the minimum gives 4 as the output. Then, the 4th query deletes 4 from the heap, and the 5th query gives 9 as the output.
a. Implement it with Linked List (heap_linkedlist.cpp)
b. Implement it with binary heap tree (heap_binary_tree.cpp)
__________________________________________
#include
#include
#include
#include
#include
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Explanation / Answer
// C++ Program to Implement with Binary Heap tree
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
/*
* Class Declaration
*/
class BinaryHeap
{
private:
vector <int> heap;
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BinaryHeap()
{}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void DisplayHeap();
int Size();
};
/*
* Return Heap Size
*/
int BinaryHeap::Size()
{
return heap.size();
}
/*
* Insert Element into a Heap
*/
void BinaryHeap::Insert(int element)
{
heap.push_back(element);
heapifyup(heap.size() -1);
}
/*
* Delete Minimum Element
*/
void BinaryHeap::DeleteMin()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
/*
* Extract Minimum Element
*/
int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}
/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end())
{
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
/*
* Return Left Child
*/
int BinaryHeap::left(int parent)
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
/*
* Return Right Child
*/
int BinaryHeap::right(int parent)
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
/*
* Return Parent
*/
int BinaryHeap::parent(int child)
{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
/*
* Heapify- Maintain Heap Structure bottom up
*/
void BinaryHeap::heapifyup(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
int temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}
/*
* Heapify- Maintain Heap Structure top down
*/
void BinaryHeap::heapifydown(int in)
{
int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0 && heap[in] > heap[child])
{
int temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}
/*
* Main Contains Menu
*/
int main()
{
BinaryHeap h;
int n;
cout<<"Enter no of queries"<<endl;
cin>>n;
for(i=0;i<n;i++)
{
cout<<"------------------"<<endl;
cout<<"Operations on Heap"<<endl;
cout<<"------------------"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Print Heap"<<endl;
cout<<"5.Exit"<<endl;
int choice, element;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>element;
h.Insert(element);
break;
case 2:
h.DeleteMin();
break;
case 3:
cout<<"Minimum Element: ";
if (h.ExtractMin() == -1)
{
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.DisplayHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
// A C++ program to demonstrate using linked list
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
// Constructor
MinHeap(int capacity);
// to heapify a subtree with root at given index
void MinHeapify(int );
int parent(int i) { return (i-1)/2; }
// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }
// to extract the root which is the minimum element
int extractMin();
// Returns the minimum key (key at root) from min heap
int getMin() { return harr[0]; }
// Deletes a key stored at index i
void deleteKey(int i);
// Inserts a new key 'k'
void insertKey(int k);
};
// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(int cap)
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
// Inserts a new key 'k'
void MinHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << " Overflow: Could not insertKey ";
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}
// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
// This function deletes key at index i calls extractMin()
void MinHeap::deleteKey()
{
extractMin();
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Driver program to test above functions
int main()
{
int n;
cout<<"Enter no of queries"<<endl;
cin>>n;
MinHeap h(n);
for(i=0;i<n;i++)
{
cout<<"------------------"<<endl;
cout<<"Operations on Heap"<<endl;
cout<<"------------------"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Extract Minimum Element"<<endl;
cout<<"3.Delete Minimum Element"<<endl;
cout<<"4.Exit"<<endl;
int choice, element;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>element;
h.insertKey(element);
break;
case 2:
h.DeleteKey();
break;
case 3:
cout<<"Minimum Element: ";
if (h.extractMin() == -1)
{
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.extractMin()<<endl;
break;
case 4:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.