Latest Tutorials| Questions and Answers|Ask Questions?|Site Map



Home Java Beginners Arrayexamples Heap Sort in Java

Related Tutorials


 
 

Share on Google+Share on Google+

Heap Sort in Java

Advertisement
Heap Sort in Java is used to sort integer values of an array. Like quicksort, insertion sort, bubble sort and other sorting methods, heap sort is used to sort an unsorted list.

Heap Sort in Java is used to sort integer values of an array. Like quicksort, insertion sort, bubble sort and other sorting methods, heap sort is used to sort an unsorted list. When compared to other sorting methods heap sort is the slowest but is more efficient and reliable in large data sets. In heap sort, an array can be divided in two parts: a heap (which has the unsorted list) and a sorted array.

Heap is of two types:

  1. Max heap: Max heap is a binary tree that has roots greater than its child roots.
  2. Min heap: Min heap has minimum roots than its child roots.

Min heap and Max heap decide the direction of sorted array.

In heap sorting algorithm the heap build is used to rebuild the heap.

The complexity of the heap sort is O(n.log n).

In the following example, Build Heap algorithm is used that removes the biggest element from a heap and place it in the second array. These steps are followed till all elements in heap are replaced into array.

Steps in heap sort:

  1. The Root node is replaced by the rightmost leaf.
  2. Store the root node in an array.
  3. Re-check the heap for the biggest element
  4. Repeat steps 1 and 3 until values in heap is not 0.

Example of Heap Sort in Java:

public class eap_Sort{
  public static void main(String a[]){
  int i;
  int arr[] = {1,3,4,5,2};

  System.out.println("\n  Heap Sort\n---------------\n");
  System.out.println("\n  Unsorted Array\n\n");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  for(i=arr.length; i>1; i--){
  fnSortHeap(arr, i - 1);
  }
  System.out.println("\n  Sorted array\n---------------\n");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  }

  public static void fnSortHeap(int array[], int arr_ubound){
  int i, o;
  int lChild, rChild, mChild, root, temp;
  root = (arr_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 <= arr_ubound) && (rChild <= arr_ubound)){
  if(array[rChild] >= array[lChild])
  mChild = rChild;
  else
  mChild = lChild;
  }
  else{
  if(rChild > arr_ubound)
  mChild = lChild;
  else
  mChild = rChild;
  }

  if(array[i] < array[mChild]){
  temp = array[i];
  array[i] = array[mChild];
  array[mChild] = temp;
  }
  }
  }
  temp = array[0];
  array[0] = array[arr_ubound];
  array[arr_ubound] = temp;
  return;
  }
}}

Output:

C:\array\sorting>Javac heap_Sort.java
C:\array\sorting>java heap_Sort

Heap Sort
---------------
Unsorted Array
1 3 4 5 2
Sorted array
---------------
1 2 3 4 5

Advertisement

If you enjoyed this post then why not add us on Google+? Add us to your Circles



Liked it!  Share this Tutorial


Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Posted on: May 9, 2013

Related Tutorials

Discuss: Heap Sort in Java  

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments:0
DMCA.com