PengurutanLanjutFase E–FE1E5

Heap Sort (dengan Pohon)

Heap Sort mengurutkan array dengan terlebih dulu membangunnya menjadi max heap (akar selalu nilai terbesar), lalu berulang kali menukar akar ke posisi akhir dan memperbaiki heap yang menyusut lewat sift_down. Setiap ekstraksi menempatkan nilai terbesar berikutnya ke bagian terurut, menghasilkan urutan menaik. Visualisasi menampilkan struktur pohon biner beserta array-nya, memperlihatkan proses swap dan sift_down hingga seluruh elemen terurut menaik.

Contoh kasus

Pengurutan data dengan jaminan kompleksitas O(n log n) pada sistem yang butuh performa stabil tanpa memori tambahan besar.

Silabus

Membangun max-heap agar nilai terbesar selalu di akar, lalu berulang menariknya ke belakang sambil memperbaiki heap.

Tujuan Belajar

·Memahami sifat max-heap: akar selalu nilai terbesar
·Menjelaskan proses sift_down/heapify menjaga struktur heap
·Menerapkan ekstraksi berulang untuk menghasilkan urutan menaik

Cara Kerja

·Susun array menjadi max-heap sehingga akar bernilai terbesar
·Tukar akar ke posisi paling akhir yang belum terurut
·Kecilkan ukuran heap satu langkah
·Perbaiki heap lewat sift_down agar akar kembali terbesar
·Ulangi hingga seluruh elemen tersusun menaik

Prasyarat

·Array
·Pohon biner
·Rekursi

Contoh Nyata

·Antrian prioritas penjadwal tugas di HP: proses penting jalan duluan
·Mengurutkan data besar dengan performa stabil tanpa memori tambahan

Kompleksitas O(n log n)