Heap Sort In Java

Introduction

In today's article we discuss Heap Sort In Java.

What is Heap?

The heap data structure is an array object that can be easily visualized as a complete Binary Tree. There are two types of heaps. The first one is a Max Heap and the second one is a Min Heap. A Max Heap is a special type of Binary Tree. The roots of the Max Heap is greater than its child roots. The other heap is a Min Heap that is also a special type of heap that has a lower value root than his child. We can sort the array values using a Heap Sorting algorithm. In this algorithm the heap that is built is used to rebuild the heap. The complexity of the Heap Sort is O(n.log(n)). A Heap Sort is slowest but it is the better option for large data sets.  All nodes of the heap also satisfy the relation that the key value at each node is at least as large as the value as its children.

                                                           

             fig-max-heap                                                                                            fig-min-heap

Advantages of Heap-Sort

1. The Heap Sort algorithm exhibits consistent performance. As in the worst case performance, best case performance, average case performance comlexity are the same, O(n log n)
2. The Heap Sort algorithm is very efficient. It is efficient for sorting a large number of elements. This implies that no other sorting algorithms can perform better in comparison.
3. Memory usage is minimal. In contrast, the Merge Sort algorithm requires more memory space. Similarly, the Quicksort algorithm requires more stack space due to its recursive nature.
4. The Heap Sort algorithm is simpler to understand than other equally efficient sorting algorithms, because it does not use recursion.

Limitations

1. It is not a stable sort.
2. It requires more processing time.

Heap Sort Algorithm

1. Arrange the nodes in the Binary Tree form.
2. The nodes should be arranged as per the specific rules.
3. The user inputs the size of the heap within a specified limit. The program generates a corresponding Binary Tree with nodes having randomly generated key values.
4. Generate Heap Operation: Let "n" be the number of nodes in the tree and "i" be the key of a tree. For this, the program uses an operation called "Heapify". When Heapify is called both the left and right subtree of the "i" are heaps. The function of Heapify is to let "i" settle down to a position by swapping itself with the larger of its children.
5. Remove maximum element: The program removes the largest element of the heap of the root by swapping it with the last element.
6. The program executes Heapify (new root) so that the resulting tree satisfies the heap property.
7. Repeat steps 3 to step 6 until the heap is empty.

Example-1

This example shows that how the Heap Sort works.

Consider the numbers 76, 21, 20, 95, 16, 19, 45, 45, 23 for sorting using the heap.

1. At first, we pick up the first element 76 from the list. Make it as the root node.
2. Next, take the second element 21 from the list. Insert this to the left of the root node 76.
3. Then, take the third element 20 from the list for insertion. Insert it to the right of the root node.
4. Take the fourth element 95. Insert it to the left side node 21. The inserted element is greater than the parent element, hence swap the 95 with 21. But the parent node 76 is smaller than the child node 95 hence 95 and 76 are swapped. After swapping 95 becomes the root node.
5. Consider the next element 16 to insert in the tree. Insert it at the left side. There exists the left node, hence insert it to the right of the 76.
6. Element 19 is inserted to the right side of 95 because the left side becomes full. Insert the element 19 to the left of node 20.
7. Now, element 45 is to be inserted at the right side of 20. However, the parent element has the value lesser than the child element hence swap the 45 with 20.
8. Now, the right side is fully filled hence add the next element 45 to the left. The element 45 is inserted at the last node of the left, i.e. 21. However, the parent element has the value lesser than the child element hence swap 45 with 21.
9. Insert the last element 23 to the left side node, which is 45. The left of the 45 is already filled, hence insert the element 23 at the right of the 45.
10. At last, we get a sorted heap tree.

Sample program for Heap Sort

public class HeapSortEx
  {
    public static void main(String a[])
      {
        int i;
        //Numbers which are to be sorted
        int n[]={23,43,12,34,17,177,25};
        //Displays the numbers before sorting
        System.out.print("Before sorting, numbers are ");
        for(i=0;i<n.length;i++)
          {
            System.out.print(n[i]+" ");
          }
        System.out.println();
        //Sorting in ascending order using Heap Sort
        for(i=n.length; i>1; i--)
          {
            initializeheapSort(n, i-1);
          }
        //Displaying the numbers after sorting
        System.out.print("After sorting, numbers are ");
        for(i=0;i<n.length;i++)
          {
            System.out.print(n[i]+" ");
          }
      }
    public static void initializeheapSort(int n[], int n_ubound)
      {
        int i, o;
        int lChild, rChild, mChild, root, temp;
        root=(n_ubound-1)/2;
        for(o=root;o>=0;o--)
          {
            for(i=root;i>=0;i--)
              {
                lChild=(2*i)+1;
                rChild=(2*i)+2;
                if((lChild<=n_ubound) && (rChild <= n_ubound))
                  {
                    if(n[rChild]>=n[lChild])
                    mChild=rChild;
                    else
                    mChild=lChild;
                  }
                else
                  {
                    if(rChild>n_ubound)
                    mChild=lChild;
                    else
                    mChild=rChild;
                  }
                if(n[i]<n[mChild])
                  {
                    temp=n[i];
                    n[i]=n[mChild];
                    n[mChild]=temp;
                  }
              }
          }
        temp=n[0];
        n[0]=n[n_ubound];
        n[n_ubound] = temp;
        return;
      }
  }

Output