Binary Heap in C++ - Sanfoundry

This C++ Program demonstrates the implementation of Binary Heap.

Here is source code of the C++ Program to demonstrate Binary Heap. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Binary Heap

```
 */
```
```
#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;
```
```
    while (1)
```
```
    {
```

        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;
```
```
}
```

$ g++ heap.cpp
$ a.out
/*
------------------
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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Binomial Heap

» Next - C++ Program to Implement D-ary Heap

Related Posts:

Check Programming Books
Check Computer Science Books
Check Data Structure Books
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: