Code:
#include iostream
#include cstdlib
#include vector
#include iterator
using namespace std;
/*
* Class Declaration
*/
class BinaryHeap
{
private:
vector
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"<
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<
}
/*
* Extract Minimum Element
*/
int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}
/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector
cout<<"Heap --> ";
while (pos != heap.end())
{
cout<<*pos<<" ";
pos++;
}
cout<
}
/*
* 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;
while (1)
{
cout<<"------------------"<
cout<<"Operations on Heap"<
cout<<"------------------"<
cout<<"1.Insert Element"<
cout<<"2.Delete Minimum Element"<
cout<<"3.Extract Minimum Element"<
cout<<"4.Print Heap"<
cout<<"5.Exit"<
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"<
}
else
cout<<"Minimum Element: "<
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.DisplayHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<
}
}
return 0;
}
Output:
/*
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 4 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 4 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 4 9 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element: 3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 4 9 7 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 4 9 7 5 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 2 4 3 7 5 11 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 4 11 7 5 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element: 3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 4 5 11 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element: 4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 5
------------------
(program exited with code: 0)
Press return to continue
More C++ Programs:
