Antrian Prioritas dalam Struktur Data: Semua yang Perlu Anda Ketahui

pengantar

Antrian prioritas dalam struktur data merupakan bentuk penting dari ADT (Abstract Data Types). Setiap elemen diberikan prioritas, yang berfungsi sebagai karakteristik untuk mendefinisikan dan mengaturnya.

ADTS adalah bagian dari domain ilmu data, di mana struktur data digunakan sebagai pola pengaturan untuk menyimpan informasi dan mengelola operasi seperti akses, penambahan, pencarian, dan modifikasi nilai data. Metodologi yang digunakan untuk pengaturan data ini mengarahkan cara mereka diatur. Struktur data juga menentukan arah aliran data dan hubungan yang dibagi dalam elemen sistem.

Para ahli memperkirakan bahwa pada tahun 2025, total data global dapat melampaui 175 zettabytes. Untuk mengelola data dalam jumlah besar, struktur data digunakan untuk menangani database besar dan tujuan pengindeksan secara efisien. Berbagai macam struktur data seperti tumpukan, antrian, array, tumpukan, dll, digunakan selama tahap pemrograman. Tumpukan dan antrian adalah bentuk linier dari struktur data, karena data disimpan secara berurutan, satu demi satu. Mereka tidak memiliki cabang, dan setiap elemen/nilai data harus diatur dalam garis lurus.

Pengaturan Tumpukan dan Antrian

Stack mengikuti pendekatan LIFO (Last In First Out) untuk pengaturan penyimpanan, sedangkan antrian mengikuti pengaturan FIFO (First In First Out). Ini merupakan faktor penting untuk membedakan antara dua struktur data linier ini. Aplikasi mereka diputuskan berdasarkan pendekatan LIFO/FIFO mereka, karena mereka bergantung pada penggunaan komputasi yang unik.

Untuk mempelajari lebih lanjut tentang ilmu data dan contoh struktur data, daftarlah di PG Diploma dalam Big Data, yang diselenggarakan oleh upGrad.com .

Untuk antrian, FIFO menetapkan bahwa ketika beberapa item ditambahkan ke sistem, item pertama yang ditambahkan akan menjadi yang pertama diakses/dihapus.

5 Operasi Dasar yang Dapat Dilakukan pada Antrian

1. Enqueue: Operasi ini dilakukan ketika kita ingin menambahkan elemen ke antrian.

2. Dequeue: Operator ini digunakan untuk menghapus elemen dari antrian.

3. IsEmpty: Operasi ini digunakan untuk memeriksa apakah antrian kosong, dan tidak ada lagi dequeue yang memungkinkan.

4. IsFull: Operator ini memeriksa apakah antrian sudah penuh dan tidak dapat menangani penambahan enqueue lebih lanjut.

5. Peek: Operator Peek hanya mengingat/menampilkan nilai/elemen data yang diharapkan dari antrian tanpa menghapusnya dari urutan yang dialokasikan.

Pelajari mengapa Ilmu Data penting dan menambah nilai bisnis melalui blog informatif dari upGrad.com ini.

Antrian Prioritas dalam Struktur Data

Antrian prioritas memiliki prioritas tambahan yang terkait dengan masing-masing elemennya. Mereka tidak mengikuti pendekatan FIFO seperti antrian tradisional. Sebaliknya, antrian prioritas dalam struktur data diatur sedemikian rupa sehingga elemen 'prioritas tinggi' dilayani sebelum rekan-rekan 'prioritas rendah' ​​mereka.

Nilai elemen sering dipertimbangkan saat mengalokasikan nilai prioritas padanya. Antrian prioritas berbeda dari antrian tradisional dengan cara di mana elemen dengan prioritas tertinggi akan diambil terlebih dahulu ketika kami mencoba untuk menghapus elemen berikutnya dari antrian.

Prasyarat lain dari antrian prioritas adalah bahwa data yang dimasukkan dalam antrian ini harus diurutkan secara berurutan. Ini berarti bahwa elemen data individual harus dapat dibandingkan satu sama lain sedemikian rupa sehingga susunannya dapat diurutkan dari lebih rendah ke lebih besar atau lebih besar ke lebih rendah. Hal ini diperlukan untuk mengalokasikan elemen antrian dengan prioritas relatif, berdasarkan perbandingan satu sama lain.

Penerapan antrian prioritas dalam struktur data biasanya melibatkan kombinasinya dengan struktur data tidak berurutan lainnya seperti tumpukan, larik, daftar tertaut, atau BST. Heaps menyediakan bentuk kombinasi yang paling efisien karena ketentuan untuk mengimplementasikan antrian prioritas secara efektif.

Untuk mempelajari lebih lanjut tentang bidang Ilmu Data yang muncul dan aplikasinya di industri manufaktur, lihat blog terperinci ini oleh upGrad.com.

Operasi yang Didukung dalam Antrian Prioritas

Operasi dalam antrian prioritas membantu memproses informasi yang dimasukkan, dihapus, dilihat, dan diubah. Operasi ini juga berguna untuk melintasi antara elemen antrian. Mereka adalah sebagai berikut:

1. Is_empty : operasi is_empty memeriksa apakah antrian menampung elemen apa pun saat ini.

2. Sisipkan_dengan_prioritas: Operasi ini menambahkan elemen ke antrian, bersama dengan nilai prioritas yang perlu dikaitkan dengannya.

3. Pull_highest_priority_element: Operasi ini menghapus elemen dengan prioritas tertinggi dari antrian sambil mengembalikan nilai elemen tersebut.

4. Peek: Operasi Peek digunakan untuk 'find-max', atau 'find-min', tergantung pada hasil yang diharapkan. Operasi ini tidak menghapus elemen max/min dan hanya mengembalikannya.

Manfaat Menggunakan Heaps untuk Prioritas Antrian dalam Struktur Data

Kinerja O(log n) diamati untuk penyisipan dan penghapusan ketika antrian prioritas didasarkan pada tumpukan. Ini meningkatkan kinerja, dan fungsi O(n) dibangun dari set elemen 'n'. Memasangkan tumpukan dan tumpukan Fibonacci memberikan batas yang lebih baik untuk operasi antrian prioritas.

Untuk mempelajari secara mendalam tentang antrian prioritas dalam struktur data dan banyak konsep penting lainnya yang terkait dengan domain pemrograman, daftarkan diri Anda di kursus online di upGrad .

Antrian Prioritas dan Elemen Penyortiran

Anjak dalam kompleksitas komputasi, antrian prioritas sesuai dengan algoritma pengurutan karena properti yang melekat. Misalnya, kita harus mengumpulkan semua elemen yang memerlukan pengurutan, dan kemudian kita harus memasukkannya ke dalam antrian prioritas.

Kemudian, jika kita menghapus elemen secara berurutan, hasilnya akan menjadi urutan elemen yang diurutkan. Heapsort, Smoothsort, Selection Sort, Insertion Sort, dan Tree sort adalah nama dari beberapa algoritma pengurutan yang memiliki korelasi setara dengan antrian prioritas dalam struktur data.

Penerapan Antrian Prioritas

Antrian prioritas dalam struktur data biasanya diimplementasikan dalam kombinasi dengan struktur data Heap. Mereka digunakan dalam simulasi untuk mengurutkan, menyortir, dan melacak rute yang belum dijelajahi. Dua jenis antrian prioritas: Ascending dan Descending, memiliki kegunaannya sendiri. Beberapa aplikasi tersebut adalah:

• Manajemen Bandwidth
• Simulasi Acara Diskrit
• Algoritma Dijkstra
• Pengkodean Huffman
• Algoritma Pencarian Terbaik Pertama
• Algoritma Triangulasi MEKAR
• Algoritma Prim untuk pohon merentang minimum

Kesimpulan

Sampai hari ini, sekitar 5 miliar konsumen terhubung secara langsung dan tidak langsung ke data. Pada tahun 2025, lebih dari 6 miliar orang akan terhubung ke data besar. IDC memperkirakan peningkatan 10 kali lipat untuk data dan memproyeksikan permintaan tinggi untuk ilmuwan data. Antrian Prioritas dalam struktur data adalah konsep penting bagi pemrogram dan ilmuwan data karena korelasi dan aplikasinya yang erat dengan struktur data heap.

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Diploma PG IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1- on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.

Mendaftar dalam kursus Master Internasional online di bidang Ilmu Komputer dari Liverpool John Moores University , atau kursus PGD dalam kursus pengembangan perangkat lunak Full Stack , DevOps, dll., dapat meningkatkan prospek pekerjaan Anda sebagai seorang programmer.

Pelajari kursus ilmu data online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.