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