cpp codes

Method overloading vs Method Overriding

Difference between Method Overloading vs Method overriding: Overloading can occur without inheritance. Overriding of functions occurs when one class is inherited from another class.   Overloaded functions must differ in function signature i.e. either number of parameters or type of parameters should differ. In overriding, function signatures must be same.   Overloaded functions are in same … Read more

C++ Program for Tower of Hanoi

What is Tower of Hanoi? The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower, and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat … Read more

Program to implement Heap C++

Here is the source code of the program to implement heap C++ programming language.

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;

// Class Declaration
class Heap
{
    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:
        Heap()
        {}
        void Insert(int element);
        void DeleteMin();
        int ExtractMin();
        void DisplayHeap();
        int Size();
};

// Return Heap Size
int Heap::Size()
{
    return heap.size();
}


// Insert Element into a Heap
void Heap::Insert(int element)
{
    heap.push_back(element);
    heapifyup(heap.size() -1);
}

// Delete Minimum Element
void Heap::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 Heap::ExtractMin()
{
    if (heap.size() == 0)
    {
        return -1;
    }
    else
        return heap.front();
}

// Display Heap
void Heap::DisplayHeap()
{
    vector <int>::iterator pos = heap.begin();
    cout<<"Heap -->  ";
    while (pos != heap.end())
    {
        cout<<*pos<<" ";
        pos++;
    }
    cout<<endl;
}

// Return Left Child
int Heap::left(int parent)
{
    int l = 2 * parent + 1;
    if(l < heap.size())
        return l;
    else
        return -1;
}

// Return Right Child
int Heap::right(int parent)
{
    int r = 2 * parent + 2;
    if(r < heap.size())
        return r;
    else
        return -1;
}

// Return Parent
int Heap::parent(int child)
{
    int p = (child - 1)/2;
    if(child == 0)
        return -1;
    else
        return p;
}

// Heapify- Maintain Heap Structure bottom up
void Heap::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 Heap::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)
    {
        int temp = heap[in];
        heap[in] = heap[child];
        heap[child] = temp;
        heapifydown(child);
    }
}

// Main Contains Menu
int main()
{
    Heap 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;
}

Sample 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 to implement Hash Tables C++

What is Hash Table

Program to implement Hash Tables C++

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int TABLE_SIZE = 128;

/*
 * HashEntry Class Declaration
 */
class HashEntry
{
    public:
        int key;
        int value;
        HashEntry(int key, int value)
        {
            this->key = key;
            this->value = value;
        }
};

/*
 * HashMap Class Declaration
 */
class HashMap
{
    private:
        HashEntry **table;
    public:
        HashMap()
    {
            table = new HashEntry * [TABLE_SIZE];
            for (int i = 0; i< TABLE_SIZE; i++)
            {
                table[i] = NULL;
            }
        }
        /*
         * Hash Function
         */
        int HashFunc(int key)
        {
            return key % TABLE_SIZE;
        }
        /*
         * Insert Element at a key
         */
    void Insert(int key, int value)
    {
            int hash = HashFunc(key);
            while (table[hash] != NULL && table[hash]->key != key)
            {
                hash = HashFunc(hash + 1);
            }
            if (table[hash] != NULL)
                delete table[hash];
            table[hash] = new HashEntry(key, value);
    }
        /*
         * Search Element at a key
         */
        int Search(int key)
    {
        int  hash = HashFunc(key);
        while (table[hash] != NULL && table[hash]->key != key)
        {
            hash = HashFunc(hash + 1);
        }
        if (table[hash] == NULL)
            return -1;
        else
            return table[hash]->value;
        }

        /*
         * Remove Element at a key
         */
        void Remove(int key)
    {
        int hash = HashFunc(key);
        while (table[hash] != NULL)
        {
            if (table[hash]->key == key)
                break;
            hash = HashFunc(hash + 1);
        }
            if (table[hash] == NULL)
        {
                cout<<"No Element found at key "<<key<<endl;
                return;
            }
            else
            {
                delete table[hash];
            }
            cout<<"Element Deleted"<<endl;
        }
        ~HashMap()
    {
            for (int i = 0; i < TABLE_SIZE; i++)
            {
                if (table[i] != NULL)
                    delete table[i];
                delete[] table;
            }
        }
};
/*
 * Main Contains Menu
 */
int main()
{
    HashMap hash;
    int key, value;
    int choice;
    while (1)
    {
        cout<<"n----------------------"<<endl;
        cout<<"Operations on Hash Table"<<endl;
        cout<<"n----------------------"<<endl;
        cout<<"1.Insert element into the table"<<endl;
        cout<<"2.Search element from the key"<<endl;
        cout<<"3.Delete element at a key"<<endl;
        cout<<"4.Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter element to be inserted: ";
            cin>>value;
            cout<<"Enter key at which element to be inserted: ";
            cin>>key;
            hash.Insert(key, value);
            break;
        case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>key;
            if (hash.Search(key) == -1)
            {
            cout<<"No element found at key "<<key<<endl;
            continue;
        }
        else
        {
            cout<<"Element at key "<<key<<" : ";
            cout<<hash.Search(key)<<endl;
        }
            break;
        case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>key;
            hash.Remove(key);
            break;
        case 4:
            exit(1);
        default:
           cout<<"nEnter correct optionn";
       }
    }
    return 0;
}

Sample Output:

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 12
Enter key at which element to be inserted: 1

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 24
Enter key at which element to be inserted: 2

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 36
Enter key at which element to be inserted: 3

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 48
Enter key at which element to be inserted: 4

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 60
Enter key at which element to be inserted: 5

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
Element at key 3 : 36

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 5
Element at key 5 : 60

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 4
Element Deleted

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 4
No element found at key 4

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 2
Element at key 2 : 24

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4


------------------

Priority Queue in STL implementation in C++

In this post first we will understand what a Priority Queue is and then we will write a program in C++ to implement Priority Queue in STL. Let’s understand what a Priority Queue is.

Priority queue:

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the “back” of the specific container, which is known as the top of the priority queue.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following operations:

  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()

C++ program to implement Priority Queue in STL:

#include <iostream>
#include <queue>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
    priority_queue<int> pq;
    int choice, item;
    while (1)
    {
        cout<<"\n---------------------"<<endl;
        cout<<"Priority Queue in Stl"<<endl;
        cout<<"\n---------------------"<<endl;
        cout<<"1.Insert Element into the Priority Queue"<<endl;
        cout<<"2.Delete Element from the Priority Queue"<<endl;
        cout<<"3.Size of the Priority Queue"<<endl;
        cout<<"4.Top Element of the Priority Queue"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter value to be inserted: ";
            cin>>item;
            pq.push(item);
            break;
        case 2:
            item = pq.top();
            if (!pq.empty())
            {
                pq.pop();
                cout<<"Element "<<item<<" Deleted"<<endl;
            }
            else
            {
                cout<<"Priority Queue is Empty"<<endl;
            }
            break;
        case 3:
            cout<<"Size of the Queue: ";
        cout<<pq.size()<<endl;
            break;
        case 4:
            cout<<"Top Element of the Queue: ";
            cout<<pq.top()<<endl;
            break;
        case 5:
            exit(1);
        break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

 

Sample Output:
---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 5

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 3

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 7

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 4

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 2

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 8

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 3
Size of the Queue: 6

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 4
Top Element of the Queue: 8

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 2
Element 8 Deleted

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 3
Size of the Queue: 5

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 4
Top Element of the Queue: 7

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 5


------------------