BINARY HEAP

AIM: To implement operations on binary heap.
i) Vertex insertion
ii) Vertex deletion
iii) Finding vertex
iv) Edge addition and deletion
SOURCE CODE:
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
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();
};
int BinaryHeap::Size()
{
    return heap.size();
}
void BinaryHeap::Insert(int element)
{
    heap.push_back(element);
    heapifyup(heap.size() -1);
}
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;
}
int BinaryHeap::ExtractMin()
{
    if (heap.size() == 0)
    {
        return -1;
    }
    else
        return heap.front();
}
void BinaryHeap::DisplayHeap()
{
    vector <int>::iterator pos = heap.begin();
    cout<<"Heap --> ";
    while (pos != heap.end())
    {
        cout<<*pos<<" ";
        pos++;
    }
    cout<<endl;
}
int BinaryHeap::left(int parent)
{
    int l = 2 * parent + 1;
    if (l < heap.size())
        return l;
    else
        return -1;
}
int BinaryHeap::right(int parent)
{
    int r = 2 * parent + 2;
    if (r < heap.size())
        return r;
    else
        return -1;
}
int BinaryHeap::parent(int child)
{
    int p = (child - 1)/2;
    if (child == 0)
        return -1;
    else
        return p;
}
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));
    }
}
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);
    }
}
int main()
{
    BinaryHeap h;
    int choice, element;
    while (1)
    {
        cout<<"Operations on Heap"<<endl;
        cout<<"1.Insert Element\n2.Delete Minimum Element\n3.Extract Minimum Element\n4.Display\n5.Exit"<<endl;
        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:
                if (h.ExtractMin() == -1)
                    cout<<"Heap is Empty"<<endl;
                else
                    cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
                break;
            case 4:
                cout<<"Heap Elements are: ";
                h.DisplayHeap();
                break;
            case 5:
                exit(1);
            default:
                cout<<"Enter Correct Choice"<<endl;
        }
    }
    return 0;

}
OUTPUT:
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 1
Enter the element to be inserted: 10
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
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.Display
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.Display
5.Exit
Enter your choice: 1
Enter the element to be inserted: 60
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 1
Enter the element to be inserted: 15
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 1
Enter the element to be inserted: 23
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 4
Heap Elements are: Heap --> 2 10 5 60 15 23
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 3
Minimum Element: 2
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 2
Element Deleted
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit
Enter your choice: 4
Heap Elements are: Heap --> 5 10 23 60 15
Operations on Heap
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Display
5.Exit

Enter your choice: 5