Loading Posts...

C++ Heap Sort Example | Heap Sort Program In C++

C++ Heap Sort Example | Heap Sort Program In C++

C++ Heap Sort Example | Heap Sort Program In C++ is today’s topic. Heap Sort is a sorting method based on comparisons between the elements. This method works on the principle of binary heap data structure.  A binary heap data structure is much similar to the binary tree. A binary heap is a binary tree in which the elements are stored in a particular tree-like structure. In this, the parent node is either greater (or smaller) than the values stored in the child nodes. According to this, the heaps are either called max heap or min-heap, respectively.

We have already covered QuickSort, MergeSort, and BubbleSort in C++ in this blog.

C++ Heap Sort

Heapsort is a comparison based sorting technique based on a Binary Heap data structure. It is similar to the selection sort where we first find the maximum element and place a maximum element at the end. We repeat a same process for the remaining item.

Heap sorting method is quite similar to the selection sort. Just like selection sort, in this too the largest element among the values is selected and then placed at the end of the value list (in case of ascending order sorting).

#What is a Binary Heap

Let us first define the Complete Binary Tree. The complete binary tree is a binary tree in which every level, except possibly the last, is filled, and all nodes are as far left as possible.

The Binary Heap is a Complete Binary Tree where elements are stored in a unique order such that value in the parent node is greater(or smaller) than the values in its two children nodes.

The former is called max heap, and the latter is called min-heap. The binary tree or array can represent the heap.

#Reasons for using Array Data Structure

In this sorting method, we use array data structures. It is mainly due to two significant reasons :

  1. Array data structures are quite fast and space-efficient. Since in array data structures, the elements are stored in contiguous memory blocks, and we don’t have to store the memory addresses of every element. It thereby decreases the space required for storing the same number of items as compared to other data structures.
  2. Arrays are also used here because it gets too easy to access the child nodes if the address of the parent node is known. Let us say if the parent node is stored at an index “z” in the array, and then the child nodes will automatically be stored at 2*z+1 (for left node) and 2*z+2 (for right node). This isn’t the case with other data structures, where it becomes quite challenging to find the child nodes.

#Algorithm for Heap Sort Method

  1. Once the user has entered the values to be sorted, they are added to an array data structure. After the values have been stored, the instructions are given to make the maximum heap out of those elements.
  2. This makes the largest element to be stored at the root position of the heap. After this, the size of the heap is reduced by 1, and the last element of the heap replace the value at the root position. 
  3. Finally, the root position of the heap is heaped. This is done following the following procedure:
  4. The heapification procedure is performed from bottom to up order because a node can be heaped only if the values under it are heapify.
  5. Take an example for the values: 12, 20, 6, 15, 2

          12(0)

          /     

     20(1)   6(2)

    /     

 15(3)    2(4)

Starting the procedure with index 1:

         12(0)

          /    

    20(1)    6(2)

    /     

15(3)    2(4)

Then we are continuing with index 0:

          20(0)

          /     

     15(1)    6(2)

    /      

 12(3)    2(4)

The above steps are continued again and again recursively until the value of the heap is greater than 1.

#C++ Heap Sort Program

See the following program.

#include 
using namespace std;
void heapify(int array[], int len, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < len && array[left] > array[largest])
        largest = left;

    if (right < len && array[right] > array[largest])
        largest = right;

    if (largest != i)
    {
        swap(array[i], array[largest]);

        heapify(array, len, largest);
    }
}

void heapSort(int array[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
        heapify(array, len, i);

    for (int i = len - 1; i >= 0; i--)
    {
        swap(array[0], array[i]);
        heapify(array, i, 0);
    }
}

void print(int array[], int len)
{
    cout << "After sorting the array is: n";
    for (int i = 0; i < len; ++i)
        cout << array[i] << " ";
    cout << endl;
}

int main()
{
    int array[] = {12, 20, 6, 15, 2};
    int len = sizeof(array) / sizeof(array[0]);

    heapSort(array, len);
    print(array, len);
}

See the following output.

Finally, C++ Heap Sort Example | Heap Sort Program In C++ is over.

The post C++ Heap Sort Example | Heap Sort Program In C++ appeared first on AppDividend.

Get Free Email Updates!

Signup now and receive an email once I publish new content.

I agree to have my personal information transfered to MailChimp ( more information )

I will never give away, trade or sell your email address. You can unsubscribe at any time.

user

The author didnt add any Information to his profile yet

Leave a Comment

Loading Posts...