[Java] Heapsort implementation (in java)

2 minute read

Directory structure

heap/ ├ Heap.java └ Main.java

execute
$ javac Heap.java
$ javac Main.java
$ java Main
Source code

Heap.java


import java.util.*;
/**
 * Heap sort class
 */
public class Heap {
    int[] origArray;
    int[] origHeap;
    int[] forSortHeap;
    int[] sortedHeap;
    int arrayLength;
    /**
     * Get an array for heap sort.
     */
    public void getForSortHeap(){
        for (int i: forSortHeap){
            System.out.print(i+", ");
        }
        System.out.println();
    }
    /**
     * Get heap-sorted array
     */
    public void getSortedHeap(){
        for (int i: sortedHeap){
            System.out.print(i+", ");
        }
        System.out.println();
    }
    /**
     * Constructor. Store array data in heap array
     * @param array Initial array before sorting
     */
    public Heap(int[] array){
        arrayLength = array.length;
        this.origArray = new int[array.length];
        this.origArray = array;
        this.origHeap = new int[array.length];
        this.forSortHeap = new int[array.length];
        this.sortedHeap = new int[array.length];
        for (int i = 0; i <array.length; i++){
            insert(i);
        }
    }
    /**
     * Store idx Nth element in heap array
     * @param idxN
     */
    public void insert(int idxN){
        int idxParent = idxN;
        int nextIdxParent = 0;
        int tmp = 0;
        this.forSortHeap[idxN] = this.origArray[idxN];
        while (idxParent >= 0){
            nextIdxParent = idxParent / 2;
            if (forSortHeap[nextIdxParent] <forSortHeap[idxParent]){
                swap(forSortHeap, nextIdxParent, idxParent);
            } else {
                break;
            }
            idxParent = nextIdxParent;
        }
    }
    /**
     * Execute heap sort (delete the maximum value of heap from heap array and add to the array in order)
     */
    public void sort(){
        for (int i = 0; i <arrayLength; i++){
            sortedHeap[i] = getMax();
            removeMax(i);
        }
    }
    /**
     * Pop the maximum value in the heap and store it in a new array for heap
     * @param idxNmax for SortHeap idx (n-th max value in array will be deleted.)
     */
    public void removeMax(int idxNmax){ // n-th max value in array will be deleted.
        int idxChild = 0;
        forSortHeap[0] = forSortHeap[arrayLength-idxNmax-1];
        forSortHeap[arrayLength-idxNmax-1] = 0;
        while (2 * idxChild + 2 <arrayLength){
            if ((forSortHeap[idxChild] >forSortHeap[2 * idxChild + 1]) && (forSortHeap[idxChild] >forSortHeap[2 * idxChild + 2])){
                break;
            }
            if (forSortHeap[2 * idxChild + 1] >= forSortHeap[2 * idxChild + 2]){
                swap(forSortHeap, 2 * idxChild + 1, idxChild);
                idxChild = 2 * idxChild + 1;
            } else {
                swap(forSortHeap, 2 * idxChild + 2, idxChild);
                idxChild = 2 * idxChild + 2;
            }
        }
    }
    /**
     * Get maximum value of heap
     * @return maximum value
     */
    public int getMax(){
        return forSortHeap[0];
    }
    /**
     * Swap array elements
     * @param arr swap target array
     * @param a index 1st
     * @param b index second
     */
    public void swap(int[] arr, int a, int b){
        int tmp = 0;
        tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

Execution class

Main.java


import java.util.*;
public class Main {
    public static void main(String[] args){
        int[] a = {3,9,1,6,10,13,2,18,4,7,20};
        Heap heap = new Heap(a);
        System.out.println("getForSortHeap>>> ");
        heap.getForSortHeap();
        heap.sort();
        System.out.println("getSortedHeap>>> ");
        heap.getSortedHeap();
    }
}
Standard output
getForSortHeap>>>
20, 18, 13, 10, 7, 9, 2, 3, 1, 4, 6,
getSortedHeap>>>
20, 18, 13, 10, 9, 7, 6, 4, 3, 2, 1,
Reference