Friday, May 10, 2013
The heapsort algorithm starts by using BUILDMAXHEAP to build a maxheap on the input array A[1 : : n ],where n=A:length. Since the maximum element of the array is stored at the root A[1] , we can put it into its correct final osition by exchanging it with A[n] . If we now discard node n from the heap  and we can do so by simply decrementing A:heapsize we observe that the children of the root remain maxheaps, but the new root element might violate the maxheap property. All we need to do to restore the maxheap property, however, is call MAXHEAPIFY(A, 1), which leaves a maxheap in A[1 : : n 1] . The heapsort algorithm then repeats this process for the maxheap of size n 1 down to a heap of size 2.
The program written below has build_max_heap() to build the maxheap, max_heapify() to retain the maxheap property and heap_sort() for sorting. The most important thing of the code is that you can use this to sort anything. Just pass an array of any object which is comparable i.e. implements Comparable interface or any array of wrapper class objects like Integer, Float etc. This is only beacause we have done this using Java's generics feature to make this code generic and general and no need for different implementations.

import java.util.Scanner;
/*This code can take in any array of Comparable i.e whose data can be compared and generates the sorted elements using heap sort*/
public class HeapSort<E extends Comparable<? super E>>{
private int heap_size;
private E A[];
public HeapSort(E a[]){
A=a;
}
private void build_max_heap(){ //building maxheap
heap_size=A.length1;
for(int i=heap_size/2;i>=0;i)
max_heapify(i);
}
private void swap(int i,int j){
E tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
private void max_heapify(int i){
int l=2*i,r=2*i+1; //left and right child
int largest;
if(l<=heap_size && A[l].compareTo(A[i])>0)
largest=l;
else largest=i;
if(r<=heap_size && A[r].compareTo(A[largest])>0)
largest=r;
if(largest!=i){ //finding largest, swapping and then reheapify
swap(i,largest);
max_heapify(largest);
}
}
public E[] heap_sort(){
build_max_heap();
for(int i=A.length1;i>=0;i){
swap(0,i); //swapping with first
heap_size; //decreasing size
max_heapify(0); //reheapify
}
return A;
}
public static void main(String[] args)throws Exception{
Scanner sc=new Scanner(System.in);
System.out.print("Enter size : ");
int n=sc.nextInt();
Integer a[]=new Integer[n];
System.out.println("Enter elements to be sorted >");
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
HeapSort<Integer> obj=new HeapSort<Integer>(a);
a=obj.heap_sort();
System.out.println("Sorted array >");
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
}
The program written below has build_max_heap() to build the maxheap, max_heapify() to retain the maxheap property and heap_sort() for sorting. The most important thing of the code is that you can use this to sort anything. Just pass an array of any object which is comparable i.e. implements Comparable interface or any array of wrapper class objects like Integer, Float etc. This is only beacause we have done this using Java's generics feature to make this code generic and general and no need for different implementations.
Heapsort operation 
Java Source Code
import java.util.Scanner;
/*This code can take in any array of Comparable i.e whose data can be compared and generates the sorted elements using heap sort*/
public class HeapSort<E extends Comparable<? super E>>{
private int heap_size;
private E A[];
public HeapSort(E a[]){
A=a;
}
private void build_max_heap(){ //building maxheap
heap_size=A.length1;
for(int i=heap_size/2;i>=0;i)
max_heapify(i);
}
private void swap(int i,int j){
E tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
private void max_heapify(int i){
int l=2*i,r=2*i+1; //left and right child
int largest;
if(l<=heap_size && A[l].compareTo(A[i])>0)
largest=l;
else largest=i;
if(r<=heap_size && A[r].compareTo(A[largest])>0)
largest=r;
if(largest!=i){ //finding largest, swapping and then reheapify
swap(i,largest);
max_heapify(largest);
}
}
public E[] heap_sort(){
build_max_heap();
for(int i=A.length1;i>=0;i){
swap(0,i); //swapping with first
heap_size; //decreasing size
max_heapify(0); //reheapify
}
return A;
}
public static void main(String[] args)throws Exception{
Scanner sc=new Scanner(System.in);
System.out.print("Enter size : ");
int n=sc.nextInt();
Integer a[]=new Integer[n];
System.out.println("Enter elements to be sorted >");
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
HeapSort<Integer> obj=new HeapSort<Integer>(a);
a=obj.heap_sort();
System.out.println("Sorted array >");
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
}

Download Links

Subscribe to:
Post Comments
(Atom)
Labels
 Algorithms (7)
 Annotation (3)
 Files (6)
 Generics (3)
 Graphics2D (5)
 Graphics2DImages (7)
 Inheritance (2)
 J2EE (9)
 Java 8 (4)
 Java FAQs (19)
 JDBC (3)
 Networking (2)
 Packages (1)
 Reflection (4)
 Security (7)
 Sorting (2)
 Swing (3)
 Threads (3)
 Utils (3)
Popular Posts

Today I will show you how you can implement Bankers algorithm in Java. The Banker's algorithm is a resource allocation and deadlock a...

 UPDATE  I have updated the code on request of some followers so that they can directly...

Today I am going to show how to convert a postfix expression to an infix expression using stack in Java. In an earlier post here we ...

UPDATE I have updated my post so that now it can detect IE 11. This modification was necessary as t...

Today in this article I will tell you how to convert an infix expression to postfix expression using stack. This is an important applicat...

Today I am going to post a program that will be able to produce all the mColorings of a given graph G. What is mColoring : The problem st...

Today I am going to show you how you can generate and validate captcha. A CAPTCHA (an acronym for "Completely Automated Public Turin...

Today I will show you how to do 256bits AES encryption and decryption of a file in Java. You can write codes for AES  128bits without d...
Links
About Me

Nirupam Das
 I am a student of BTech Computer Science Engineering from RCCIIT,Kolkata. I am a crazy lover of Java and wants to settle as a Java developer. I have a seven years Java experience with an application developer experience for 2 years. Recently from March 2012 I am a registered S40 app developer for Nokia and has corrected an app of them. I am currently writing blogs to encourage and grow interest in all those who don't know or learning Java.
0 comments:
Post a Comment