Today I will explain heap sort using stl. Sorting an array using heap or making an heap is very easy. Using STL makes it a cake walk. In the following code I have used these function from STL.
First is make_heap(). Simply passing the vector inside it makes the heap.
Second is pop_back() which pops the lowest valued or last element from the heap.
Third is pop_heap(). It rearranges the elements in the heap range [first,last)
in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to (last-1)
.
While the element with the highest value is moved from first to (last-1)
(which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1)
preserves the properties of a heap.
Basically it swaps the value in the position first
and the value in the position last-1
and makes the subrange [first, last-1)
into a max heap. This has the effect of removing the first (largest) element from the heap defined by the range [first, last)
.
#include <iostream>#include <vector>
#include <algorithm>
using namespace std;
int main() {
// This is the unsorted array
int a[] = {2,4,34,344,231,556,1,31,675,78,21,43,1134,6543,12,765,897};
// We have put the array inside a vector v
vector<int> v(a,a+17);
// make_heap is an function from stl.
// Basically it creates the heap from vector v
make_heap (v.begin(),v.end());
// Using this for loop we print the last element from the heap
// We can also store the output in an array or vector or any other data structure
for(int i = 0; i<sizeof(data)/sizeof(data[0]);i++){
pop_heap (v.begin(),v.end());
cout<<v.back()<<" ";
v.pop_back();
}
return 0;
}
0 comments:
Post a Comment