Heapsort implementation (in java)

Directory structure

heap/  ├ Heap.java  └ Main.java

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

Heap.java


import java.util.*;
/**
 *Class for heapsort
 */
public class Heap {
    int[] origArray;
    int[] origHeap;
    int[] forSortHeap;
    int[] sortedHeap;
    int arrayLength;
    /**
     *Get an array for heapsort.
     */
    public void getForSortHeap(){
        for (int i: forSortHeap){
            System.out.print(i+", ");
        }
        System.out.println();
    }
    /**
     *Get a heapsorted 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 idxNth 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;
        }
    }
    /**
     *Perform heapsort (remove the maximum heap value from the heap array and add it 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 restore it in a new array for the heap
     * @idx of param idxNmax for SortHeap(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 heap
     * @return maximum value
     */
    public int getMax(){
        return forSortHeap[0];
    }
    /**
     *Swap the elements of the array
     * @param arr swap target array
     * @param a index 1st
     * @param b index 2nd
     */
    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

-[Master the sort! ~ Why Learn Sorting ~](https://qiita.com/drken/items/44c60118ab3703f7727f#7-%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD% E3% 83% BC% E3% 83% 88-% E3% 82% AA% E3% 83% B3% E3% 83% A9% E3% 82% A4% E3% 83% B3% E3% 82% AF% E3 % 82% A8% E3% 83% AA% E3% 81% AB% E3% 81% A4% E3% 81% 84% E3% 81% A6)

Recommended Posts

Heapsort implementation (in java)
Interpreter implementation in Java
Boyer-Moore implementation in Java
Implementation of gzip in java
Implementation of tri-tree in Java
Implementation of like function in Java
Partization in Java
Changes in Java 11
Rock-paper-scissors in Java
Pi in Java
FizzBuzz in Java
Implementation of DBlayer in Java (RDB, MySQL)
[java] sort in list
Read JSON in Java
Make Blackjack in Java
Rock-paper-scissors app in Java
Constraint programming in Java
Put java8 in centos7
Combine arrays in Java
"Hello World" in Java
Check Java toString () implementation
Callable Interface in Java
Comments in Java source
Azure functions in java
Format XML in Java
Simple htmlspecialchars in Java
Hello World in Java
Use OpenCV in Java
webApi memorandum in java
Type determination in Java
Ping commands in Java
Various threads in java
Zabbix API in Java
ASCII art in Java
Compare Lists in Java
POST JSON in Java
Express failure in Java
Create JSON in Java
Date manipulation in Java 8
What's new in Java 8
Use PreparedStatement in Java
What's new in Java 9,10,11
Parallel execution in Java
Initializing HashMap in Java
Try using RocksDB in Java
Read binary files in Java 1
Avoid Yubaba's error in Java
Get EXIF information in Java
Save Java PDF in Excel
[Neta] Sleep Sort in Java
Edit ini in Java: ini4j
Java history in this world
Let Java segfault in 6 lines
Try calling JavaScript in Java
Try developing Spresense in Java (1)
Try functional type in Java! ①
Create hyperlinks in Java PowerPoint
[Implementation] Java Process class notes
Implement two-step verification in Java
Refactoring: Make Blackjack in Java
Write flyway callbacks in Java