Heap In C++
Heap
data structure can be implemented in a range using STL which allows faster
input into heap and retrieval of a number always results in the largest number
i.e. largest number of the remaining numbers is popped out each time. Other
numbers of the heap are arranged depending upon the implementation.
Fig:Heap In C++ |
Operations on heap :
1. make_heap() :-
This function is used to convert a range in a container to a heap.
2. front() :-
This function displays
the first element of heap which is the maximum number.
Program
#include<bits/stdc++.h>
void main()
{
vector<int> v1 = {20, 30, 40, 25, 15};
make_heap(v1.begin(), v1.end());
cout << "The maximum element of heap is :
";
cout << v1.front() << endl;
getch();
}
Output:
The maximum element of
heap is :40
3. push_heap() :-
This function is used
to insert elements into heap. The size of the
heap is increased by 1. New element is placed appropriately in the heap.
4. pop_heap() :-
This function is used
to delete the maximum element of the heap.
The size of heap is decreased by 1. The heap elements are reorganised
accordingly after this operation.
Program:
#include<bits/stdc++.h>
#include<conio.h>
void main()
{
vector<int>
v1 = {20, 30, 40, 25, 15};
make_heap(v1.begin(),
v1.end());
cout
<< "The maximum element of heap is : ";
cout
<< v1.front() << endl;
v1.push_back(50);
push_heap(v1.begin(),
v1.end());
cout
<< "The maximum element of heap after push is : ";
cout
<< v1.front() << endl;
pop_heap(v1.begin(),
v1.end());
v1.pop_back();
cout
<< "The maximum element of heap after pop is : ";
cout
<< v1.front() << endl;
getch();
}
Output:
The maximum element of
heap is: 40
The maximum element of heap after push is:50
The maximum element of heap after pop is :40
5. sort_heap() :-
This function is used to sort the heap. After this operation, the
container is no longer a heap.
Program:
#include<bits/stdc++.h>
#include<conio.h>
void main()
{
vector<int> v1 = {20, 30, 40,
25, 15};
make_heap(v1.begin(), v1.end());
cout << "The heap elements
are : ";
for (int &x : v1)
cout << x << "
";
cout << endl;
sort_heap(v1.begin(), v1.end());
cout << "The heap elements
after sorting are : ";
for (int &x : v1)
cout << x << "
";
getch();
}
Output:
The
heap element are:40,30,20,25,15
The
heap elements after sorting are:15,20,25,30,40
6. is_heap() :-
This function is used
to check whether the container is heap or not. Returns true if container is
heap else returns false.
7. is_heap_until() :-
This function returns
the iterator to the position till the container is the heap.
Program:
#include<bits/stdc++.h>
#include<conio.h>
void main()
{
vector<int>
v1 = {40, 30, 25, 35, 15};
vector<int>::iterator
it1;
is_heap(v1.begin(),
v1.end())?
cout
<< "The container is heap ":
cout
<< "The container is not heap";
cout
<< endl;
auto it
= is_heap_until(v1.begin(), v1.end());
cout
<< "The heap elements in container are : ";
for
(it1=v1.begin(); it1!=it; it1++)
cout
<< *it1 << " ";
getch();
}
Output:
The container is not
heap
The heap elements in
container are:40,30,25
No comments:
Post a Comment