Implementasi Algoritma Heap Sort dengan Java

Untuk mengimplementasikan algoritma Heap sort pada postingan ane yg ini menggunakan bahasa pemrograman Java, gunakanlah syntax berikut ini :

import java.io.*;
import java.util.Scanner;

public class Heap
{
 public static void heapSort()
 {
  try
  {
   int elements;
   Scanner sc = new Scanner(System.in);

   System.out.println("Silahkan masukkan jumlam elemen yang diinginkan : ");
   if(sc.hasNextInt())
   {
    elements = sc.nextInt();
    int[] angka = new int[elements];
    int result = elements;
    System.out.println("--------------------------------------------------------------");

    for(int i=0; i < elements; i++)
    {
     System.out.println("Silahkan masukkan nilai untuk elemen " + i + ":");
     if(sc.hasNextInt())
     {
      angka[i] = sc.nextInt();
     }
     else
     {
      System.out.println("Maaf anda melakukan input yang salah, silahkan ulangi lagi");
      heapSort(); 
     }
    }

    /* Panggil metode build_Max_Heap */
    build_Max_Heap(angka, elements);

    /* Metode Heap Sort */
    for(int i=elements - 1; i > 0; i--)
    {
     int temp = angka[i];
     angka[i] = angka[0];
     angka[0] = temp;

     elements--;
     max_Heapfy(angka, elements, 0);
    }

    System.out.println("--------------------------------------------------------------");
    System.out.println("Hasil sorting adalah : ");

    for(int i=0; i < result; i++)
    {
     System.out.println("Index " + i + ":" + "\t" + angka[i]);
    }

    System.out.println("Apakan anda ingin melakukan sorting lagi? : (y/n)");
    String input;
    Scanner inputText = new Scanner(System.in);
    input = inputText.nextLine();
    if((input.equals("y")) || (input.equals("Y")))
    {
     heapSort();
    }
    else
    {
     System.exit(0);
    }
   }
   else
   {
    System.out.println("Maaf anda melakukan input yang salah, silahkan ulangi lagi");
    heapSort();
   }
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }

 public static void build_Max_Heap(int[] angka, int elements)
 {
  try
  {
   for(int i=(elements - 1) / 2; i >= 0; i--)
   {
    /* Memanggil metode max_Heapfy */
    max_Heapfy(angka, elements, i);
   }
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }  
 }

 public static void max_Heapfy(int[] angka, int elements, int index)
 {
  try
  {
   int left = (index + 1) * 2 - 1;
   int right = (index + 1) * 2;
   int largest;

   if(left < elements && angka[left] > angka[index])
   {
    largest = left;
   }
   else
   {
    largest = index;
   }

   if(right < elements && angka[right] > angka[largest])
   {
    largest = right;
   }

   if(largest != index)
   {
    int temp = angka[index];
    angka[index] = angka[largest];
    angka[largest] = temp;

    max_Heapfy(angka, elements, largest);
   }
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }

 public static void main(String[] args)
 {
  heapSort();
 }
}

Pada syntax tersebut terdapat 3 buah metode yaitu heapSort(), build_Max_Heap(), dan max_Heapfy(). Dimana metode heapSort adalah metode utama yang digunakan untuk melakukan sorting nilai pada array angka dengan algoritma Heap Sort, pada baris 10 sampa 33 adalah syntax untuk deklarasi array angka dan memasukkan nilai pada setiap elemen yang dimiliki array angka lalu pada baris 36 metode build_Max_Heap() dipanggil fungsi metode ini adalah membangun sebuah Heap tree agar sesuai dengan kodisi max heap.

Pada baris 86 terdapat for looping dengan kondisi i = (elements - 1)/2 (index tengah) dan selama i lebih besar sama dengan 0 maka nilai i akan berkurang 1. Dan pada baris 89 metode max_Heapfy() dipanggil, fungsi metode max_Heapfy berfungsi untuk menempatkan nilai pada sebuah index diposisi yang benar agar memenuhi kondisi max heap. Pada baris 102 dan 103 terdapat deklarasi variabel left dan right dimana kedua variabel tersebut berisi posisi left dan right child dari node index lalu pada baris 104 terdapat deklarasi variabel largest yang berisi posisi index yang memiliki nilai terbesar yang nantinya nilai tersebut akan dipindahkan ke node index. Dan pada baris 106 sampai 118 terdapat beberapa kondisi if yang berfungsi untuk membandingkan node mana yang memiliki nilai tertinggi di antara node index dan left/right child nodenya lalu pada baris 120 terdapat if yang memiliki kodisi jika largest tidak sama dengan index maka nilai pada node index dan largest bertukar tempat dan metode max_Heapfy() kembali di panggil sampai kondisi max heap terpenuhi. 

Lalu kembali ke metode heapSort() di baris 39 terdapat for looping dengan kondisi i = elements – 1 dan selama i lebih besar dari 0 maka nilai i berkurang 1. Dan pada baris 41 sampai 43 adalah syntax untuk menukar nilai pada index 0 dengan nilai di index i lalu elements dikurangi 1 disini terlihat nilai terbesar pada heap tree di index 0 ditukar posisinya dengan nilai pada index i (index terakhir) disini nilai terbesar sudah berada di index terakhir dan jumlah elements dikurangi 1 karena posisi nilai terbesar sudah berada di posisi yang benar lalu pada baris 46 metode max_Heapfy() dipanggil untuk menempatkan nilai pada index 0 pada posisi yang benar sesuai dengan kondisi max heap. Dan proses ini terus berulang selama i lebih besar dari 0  ini menadakan proses ini akan terus berjalan hingga tersisa 2 index saja yaitu index 0 dan 1. Berikut adalah hasil implementasi algoritma heap sort menggunakan Java :

 

Sekian postingan dari ane semoga bermanfaat, jika ada keasalahan mohon dikoreksi dan dimaklumi ya gan :Peace: