CodeChrist - This is a personal blog which I write to help follow coders

If you like it, feel free to comment and appreciate the good work


Following are the some features of CodeChrist

  • Easy to navigate and use.
  • You can subscibe for emails
  • CodeChrist is beautiful on every screen size (try resizing your browser!)
by

Heap sort using STL

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