Algoritma Heap Sort

Heap sort adalah teknik pengurutan berdasarkan perbandingan yang didasarkan pada struktur data Binary Heap. Algoritma ini cukup mirip dengan selection sort, di mana kita mencari elemen minimum dan menempatkan elemen minimum di awal. Kemudian, kita mengulangi proses yang sama untuk elemen yang tersisa.

Heap sort bekerja dengan memvisualisasikan elemen array sebagai jenis pohon biner lengkap khusus yang disebut heap. Misalnya, set awal angka yang kita ingin urutkan disimpan dalam array, seperti [10, 3, 76, 34, 23, 32], dan setelah pengurutan, kita mendapatkan array yang diurutkan [3,10,23,32,34,76].

Algoritma heap sort bekerja dengan menghapus elemen maksimum dan mengubah ulang sisanya dengan Sift-Down. Ini berarti algoritma ini menghapus elemen maksimum dan kemudian mengubah ulang sisanya menjadi heap.

Kompleksitas ruang heap sort adalah konstan O(1) karena penyimpanan pendukungnya. Ini berarti bahwa ruang yang dibutuhkan oleh algoritma ini tidak berubah secara signifikan tergantung pada ukuran input.

Kompleksitas waktu heap sort adalah O(n*log(n)). Ini berarti bahwa waktu yang dibutuhkan untuk mengurutkan array meningkat secara logaritmik dengan ukuran array.

Berikut adalah contoh implementasi algoritma heap sort dalam PHP:

<?php

function heapify(&$array, $n, $i)
{
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $n && $array[$left] > $array[$largest]) {
        $largest = $left;
    }

    if ($right < $n && $array[$right] > $array[$largest]) {
        $largest = $right;
    }

    if ($largest != $i) {
        swap($array, $i, $largest);
        heapify($array, $n, $largest);
    }
}

function swap(&$array, $i, $j)
{
    $temp = $array[$i];
    $array[$i] = $array[$j];
    $array[$j] = $temp;
}

function heapSort(&$array)
{
    $n = count($array);

    for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
        heapify($array, $n, $i);
    }

    for ($i = $n - 1; $i >= 0; $i--) {
        swap($array, 0, $i);
        heapify($array, $i, 0);
    }
}


$data = array(10, 3, 76, 34, 23, 32);
echo '<p>Before Sort</p>';
foreach($data as $d) {
    echo $d, ' ';
}
echo '<hr>';
echo '<p>After Sort</p>';
heapSort($data);
foreach($data as $d) {
    echo $d, ' ';
}

output

Dalam kode di atas, fungsi `heapify` digunakan untuk membuat heap. Fungsi `swap` digunakan untuk menukar dua elemen dalam array. Fungsi `heapSort` adalah fungsi utama yang mengimplementasikan algoritma heap sort.