Algoritma Pengurutan Tumpukan (Dengan Kode di Python dan C++)
Sarah Chen
Apa itu Algoritma Pengurutan Tumpukan?
Heap Sort adalah salah satu algoritma pengurutan yang populer dan lebih cepat. Itu dibangun di atas struktur data pohon biner yang lengkap. Kami akan mencari elemen maksimum dan meletakkannya di atas untuk tumpukan maksimal. Kami akan meletakkannya di simpul induk dari pohon biner.
Katakanlah sebuah array diberikan, data = [10,5, 7, 9, 4, 11, 45, 17, 60].
Dalam array, jika indeks ke-i (i=0,1,2,3 …) adalah node induk, maka (2i+1) dan (2i+2) akan menjadi turunan kiri dan kanan. Membuat pohon biner lengkap dengan array ini akan terlihat seperti ini:
Kita akan melakukan proses heapify dari awal hingga akhir array. Awalnya, jika kita mengonversi array menjadi pohon, tampilannya akan seperti di atas. Kita dapat melihat bahwa array tidak mempertahankan properti heap apa pun (min-heap atau max heap). Kita akan mendapatkan array yang diurutkan dengan melakukan proses heapify untuk semua node.
Penerapan Penyortiran Tumpukan
Berikut beberapa penggunaan algoritma heap sort:
- Konstruksi “Antrian Prioritas” memerlukan penyortiran heap. Karena heapsort menjaga elemen tetap terurut setelah setiap penyisipan dilakukan.
- Struktur Data Heap efisien dalam menemukan kth elemen terbesar dalam array tertentu.
- Kernel Linux menggunakan heap sort sebagai default algoritma penyortiran karena memiliki kompleksitas ruang O (1).
Buat Pengurutan Tumpukan dengan Contoh
Di sini, kita akan membangun tumpukan maksimal dari pohon biner lengkap berikut.
Node daun adalah 17, 60, 4, 11, dan 45. Node-node tersebut tidak memiliki node anak. Itulah sebabnya node-node tersebut disebut node daun. Jadi, kita akan memulai metode heapify dari node induknya. Berikut langkah-langkahnya:
Langkah 1) Pilih subpohon paling kiri. Jika node anak lebih besar, tukar node induk dengan node anak.
Di sini simpul induknya adalah 9. Dan simpul anaknya adalah 17 dan 60. Karena 60 adalah yang terbesar, maka 60 dan 9 akan ditukar untuk mempertahankan tumpukan maks.
Langkah 2) Sekarang, subpohon paling kiri sudah ditumpuk. Node induk berikutnya adalah 7. Induk ini memiliki dua node anak, dan yang terbesar adalah 45. Jadi, 45 dan 7 akan ditukar.
Langkah 3) Node 60 dan 4 mempunyai node induk 5. Karena “5” lebih kecil dari node anak 60, maka node tersebut akan ditukar.
Langkah 4) Sekarang, node 5 memiliki node anak 17,9. Ini tidak mempertahankan properti max heap. Jadi, 5 akan diganti dengan 17.
Langkah 5) Node 10 akan ditukar dengan 60, lalu ditukar dengan 17. Prosesnya akan terlihat seperti berikut.
Langkah 6) Hingga langkah 5, kami membuat tumpukan maksimal. Setiap node induk lebih besar dari node anaknya. Node root memiliki nilai maksimum (60).
Catatan: Untuk membuat array yang diurutkan, kita perlu mengganti node yang bernilai maksimal dengan penerusnya.
Proses ini disebut “ekstrak maks”. Karena 60 adalah node maksimal, kita akan memperbaiki posisinya ke indeks ke-0 dan membuat heap tanpa node 60.
Langkah 7) Karena 60 dihilangkan, maka nilai maksimal selanjutnya adalah 45. Kita akan melakukan proses “Extract Max” lagi dari node 45.
Kali ini kita akan mendapatkan 45 dan mengganti node root dengan penggantinya 17.
Kita perlu tampil “Ekstrak Maks” sampai semua elemen terurut.
Setelah melakukan langkah-langkah ini hingga kita mengekstrak semua nilai maksimal, kita akan mendapatkan array berikut.
Apa itu Tumpukan Biner?
Binary Heap adalah sejenis yang lengkap pohon biner struktur data. Dalam struktur pohon seperti ini, node induk lebih besar atau lebih kecil dari node anak. Jika node induk lebih kecil, maka heap disebut “Min Heap” dan jika node induk lebih besar, heap disebut “Max Heap”.
Berikut contoh min heap dan max heap.
Pada gambar di atas, jika Anda memperhatikan “Min Heap”, node induk selalu lebih kecil dari node anaknya. Di bagian kepala pohon, kita dapat menemukan nilai terkecil 10.
Demikian pula, untuk “Max Heap”, node induk selalu lebih besar dari node anak. Elemen maksimum ada di node kepala untuk “Max Heap”.
Apa itu “Heapify”?
“Heapify” adalah prinsip heap yang memastikan posisi node. Dalam Heapify, heap maksimum selalu mempertahankan hubungan dengan induk dan anak, yaitu node induk akan lebih besar daripada node anak.
Misalnya, jika node baru ditambahkan, kita perlu membentuk ulang heap. Namun, kita mungkin perlu mengubah atau menukar node atau mengatur ulang array. Proses pembentukan ulang heap ini disebut "heapify".
Berikut adalah contoh cara kerja heapify:
Berikut langkah-langkah untuk heapify:
Langkah 1) Menambahkan node 65 sebagai anak kanan dari node 60.
Langkah 2) Periksa apakah node yang baru ditambahkan lebih besar dari node induknya.
Langkah 3) Karena lebih besar dari node induk, kami menukar anak yang tepat dengan induknya.
Cara membangun Tumpukan
Sebelum membangun tumpukan atau menumpuk pohon, kita perlu tahu bagaimana kita akan menyimpannya. Karena tumpukan adalah pohon biner lengkap, lebih baik menggunakan susunan untuk menyimpan data heap.
Katakanlah sebuah array berisi total n elemen. Jika indeks ke-i merupakan simpul induk, maka simpul kiri akan berada pada indeks (2i+1), dan node kanan akan berada di index (2i+2). Kami berasumsi bahwa indeks array dimulai dari 0.
Dengan menggunakan ini, mari kita simpan tumpukan maksimum ke dalam array seperti berikut:
Algoritme heapify mempertahankan properti heap. Jika induk tidak memiliki nilai ekstrem (lebih kecil atau lebih besar), maka induk akan ditukar dengan simpul anak yang paling ekstrem.
Berikut langkah-langkah untuk menumpuk tumpukan maksimal:
Langkah 1) Mulai dari simpul daun.
Langkah 2) Temukan hasil maksimal antara orang tua dan anak.
Langkah 3) Tukar node jika node anak memiliki nilai lebih besar dari node induk.
Langkah 4) Naik satu tingkat.
Langkah 5) Ikuti langkah 2,3,4 hingga mencapai indeks 0 atau mengurutkan seluruh pohon.
Berikut pseudo-kode untuk heapify rekursif (tumpukan maks):
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Kode Pseudo untuk Pengurutan Tumpukan
Berikut kode semu untuk algoritma heap sort:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Contoh Kode Sortir Tumpukan di C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
Keluaran:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Contoh Kode Sortir Tumpukan di Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Keluaran:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Analisis Kompleksitas Waktu dan Ruang dari Heap Sort
Ada kompleksitas waktu dan kompleksitas ruang yang dapat kita analisis untuk pengurutan tumpukan. Untuk kompleksitas waktu, kita memiliki kasus berikut:
- Kasus terbaik
- Kasus Rata-rata
- Kasus terburuk
Heap diimplementasikan pada pohon biner lengkap. Jadi, di level terbawah pohon biner, akan ada jumlah node maksimum. Jika level terbawah mempunyai n node, maka level diatasnya akan memiliki n/2 node.
Dalam contoh ini, Level 3 memiliki empat item, Level 2 memiliki dua item, dan Level 1 memiliki satu item. Jika jumlah item berjumlah n, maka tinggi atau level totalnya adalah Log2(N). Jadi, memasukkan satu elemen dapat memerlukan iterasi Log(n) maksimum.
Ketika kita ingin mengambil nilai maksimum dari tumpukan, kita tinggal mengambil simpul akar. Kemudian, jalankan heapify lagi. Setiap heapify mengambil Log2(n) waktu. Mengekstraksi secara maksimal membutuhkan waktu O(1).
Kompleksitas Waktu Kasus Terbaik untuk Algoritma Heap Sort
Ketika semua elemen sudah diurutkan dalam array, dibutuhkan waktu O(n) untuk membangun heap. Karena jika daftar diurutkan maka penyisipan suatu item akan memakan waktu yang konstan yaitu O(1).
Jadi, dibutuhkan waktu O(n) untuk membuat max-heap atau min-heap dalam kasus terbaik.
Kompleksitas Waktu Kasus Rata-rata untuk Algoritma Heap Sort
Memasukkan item atau mengekstraksi item maksimum membutuhkan waktu O(log(n)). Jadi, kompleksitas waktu kasus rata-rata untuk algoritma sortir heap adalah HAI(n catatan(n)).
Kompleksitas Waktu Kasus Terburuk untuk Algoritma Heap Sort
Mirip dengan kasus rata-rata, dalam skenario terburuk, kita mungkin melakukan heapify sebanyak n kali. Setiap heapify akan menghabiskan waktu O(log(n)). Jadi, kompleksitas waktu terburuk adalah HAI(n catatan(n)).
Kompleksitas Ruang untuk Algoritma Heap Sort
Heap sort adalah algoritma yang dirancang di tempat. Ini berarti tidak diperlukan memori tambahan atau sementara untuk menjalankan tugas. Jika kita melihat implementasinya, kita akan melihat bahwa kita menggunakan swap() untuk menjalankan pertukaran node. Tidak diperlukan daftar atau array lain. Jadi, kompleksitas ruangnya adalah O(1).
