A heap is a partially sorted binary tree. Although a heap is not completely in order, it conforms to a sorting principle: every node has a value less (for the sake of simplicity, we will assume that all orderings are from least to greatest) than either of its children. Additionally, a heap is a "complete tree" -- a complete tree is one in which there are no gaps between leaves. For instance, a tree with a root node that has only one child must have its child as the left node. More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks.
Why use a heap?
A heap can be thought of as a priority queue; the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue.
C++ Implementation of Heap
Why use a heap?
A heap can be thought of as a priority queue; the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue.
C++ Implementation of Heap
/*
* C++ Program to Implement Heap
*/
#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;
}
Output of the above program:
$ 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
0 comments:
Post a Comment