java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 3947
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Heap Sort Implementation in Java E-mail
User Rating: / 132
PoorBest 

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

The following code shows how to implement heap sort in Java.

    /**
     * Standard heapsort.
     @param a an array of Comparable items.
     */
    public static void heapsortComparable [ ] )
    {
        forint i = a.length / 2; i >= 0; i-- )  /* buildHeap */
            percDowna, i, a.length );
        forint i = a.length - 1; i > 0; i-- )
        {
            swapReferencesa, 0, i );            /* deleteMax */
            percDowna, 0, i );
        }
    }

    /**
     * Internal method for heapsort.
     @param i the index of an item in the heap.
     @return the index of the left child.
     */
    private static int leftChildint )
    {
        return * i + 1;
    }

    /**
     * Internal method for heapsort that is used in
     * deleteMax and buildHeap.
     @param a an array of Comparable items.
     * @index i the position from which to percolate down.
     * @int n the logical size of the binary heap.
     */
    private static void percDownComparable [ ] a, int i, int )
    {
        int child;
        Comparable tmp;

        fortmp = a]; leftChild< n; i = child )
        {
            child = leftChild);
            ifchild != n - && achild ].compareToachild + ] ) )
                child++;
            iftmp.compareToachild ] ) )
                a= achild ];
            else
                break;
        }
        a= tmp;
    }
    
    
    /**
     * Method to swap to elements in an array.
     @param a an array of objects.
     @param index1 the index of the first object.
     @param index2 the index of the second object.
     */
    public static final void swapReferencesObject [ ] a, int index1, int index2 )
    {
        Object tmp = aindex1 ];
        aindex1 = aindex2 ];
        aindex2 = tmp;
    }

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.