Implementasi (Bagian 1)
Pelajaran 5 dari 9 dalam kursus Heap Sort, Seri DSA di Coddy.
Kita akan membangun Heap Sort mulai dari operasi intinya.
Tantangan
MudahInti dari Heap Sort adalah operasi sift-down. Mari kita buat bagian itu terlebih dahulu.
Tulis fungsi bernama siftDown yang menerima array arr (diperlakukan sebagai binary heap) dan indeks i, lalu memulihkan properti max-heap pada simpul tersebut dengan mendorongnya ke bawah. Bandingkan simpul dengan kedua anaknya pada 2*i + 1 dan 2*i + 2. Jika anak yang lebih besar memiliki nilai lebih besar, tukar simpul dengannya lalu lanjutkan dari posisi anak tersebut. Kembalikan array.
Contohnya, siftDown([1, 10, 5, 3, 2], 0) mengembalikan [10, 3, 5, 1, 2].
Coba sendiri
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Tulis kodemu di sini
*returnSize = arr_size;
return arr;
}
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Heap Sort, Seri DSA
2Algoritma
Bagaimana Cara Kerjanya?PseudocodeImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online