Heap Sort

Heap Sort in Java

Heap Sort is a comparison based sorting technique,  used for sorting linear data structures, it got it name because, it is based on Binary Heap Data Structures. Heap resembles a complete binary tree.

                                        A complete binary tree is a tree in which each parent node has exactly two child nodes, and its all the levels are completely filled, except the possible last level, in which all the nodes are as far as possible.

  • Heap sort, sorts the array by converting them into heaps, which are then converted into min heap and max heap, as  required.
  • The converted Heaps have the largest element at the top node,  and after each iteration we  remove the root node from the heap, and move it to it right position in the array, you can have a better idea on the implementation by following the pictorial representation below
heap sort(1)

Implementation Of Heap Sort

heap sort
  •  Now, since this tree is already in the max heap form, we don’t need to make any changes, we just swap the last node with the root node
  • After switching the nodes, we remove the last node of the tree
heap sort(2)
  • We have our first digit in its place.
  • Now, we,ll again create a max heap with the remaining nodes, and repeat the above procedure
heap sort(4)
heap sort(8)
heap sort(9)
heap sort(11)
heap sort(12)

Code for Heap Sort in Java


// Java program for implementation of Heap Sort
public class PrepInsta
{
//Main() for the execution of the program
public static void main(String args[])
{
int a[] = {12, 11, 13, 5, 6, 7};
int len = a.length;

PrepInsta ob = new PrepInsta();
ob.sort(a);

System.out.println("Sorted array is");
printArray(a);
}
public void sort(int a[])
{
int len = a.length;

// Build heap (rearrange array)
for (int i = len / 2 - 1; i >= 0; i--)
heapify(a, len, i);

// One by one extract an element from heap
for (int i=len-1; i>=0; i--)
{
// Move current root to end
int temp = a[0];
a[0] = a[i];
a[i] = temp;

// call max heapify on the reduced heap
heapify(a, i, 0);
}
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int a[], int len, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < len && a[l] > a[largest])
largest = l;

// If right child is larger than largest so far
if (r < len && a[r] > a[largest])
largest = r;

// If largest is not root
if (largest != i)
{
int swap = a[i];
a[i] = a[largest];
a[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(a, len, largest);
}
}

/* A utility function to print array of size n */
static void printArray(int a[])
{
int len = a.length;
for (int i=0; i<len; ++i)
System.out.print(a[i]+" ");
System.out.println();
}


}

Please Login/Signup to comment