SortingLanjutFase E–FE1E5

HEAP SORT TREE

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Array
·Pohon biner
·Rekursi

Real-World Uses

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

Complexity O(n log n)