Antrian Prioritas dalam Struktur Data: Karakteristik, Jenis & Implementasi
Diterbitkan: 2021-05-02Daftar isi
pengantar
Antrian prioritas dalam struktur data adalah perpanjangan dari antrian "normal". Ini adalah tipe data abstrak yang berisi sekelompok item. Ini seperti antrian "normal" kecuali bahwa elemen dequeuing mengikuti urutan prioritas. Urutan prioritas menurunkan item-item yang memiliki prioritas tertinggi terlebih dahulu. Blog ini akan memberi Anda pemahaman yang lebih dalam tentang antrian prioritas dan implementasinya dalam bahasa pemrograman C.
Apa itu Antrian Prioritas?
Ini adalah tipe data abstrak yang menyediakan cara untuk memelihara kumpulan data. Antrian “normal” mengikuti pola first-in-first-out. Ini menghilangkan elemen dalam urutan yang sama diikuti pada saat operasi penyisipan. Namun, urutan elemen dalam antrian prioritas tergantung pada prioritas elemen dalam antrian itu. Antrian prioritas memindahkan elemen prioritas tertinggi di awal antrian prioritas dan elemen prioritas terendah di belakang antrian prioritas.
Ini hanya mendukung elemen-elemen yang sebanding. Oleh karena itu, antrian prioritas dalam struktur data mengatur elemen baik dalam urutan menaik atau menurun.
Anda dapat menganggap antrian prioritas sebagai beberapa pasien yang mengantri di rumah sakit. Di sini, situasi pasien menentukan urutan prioritas. Pasien dengan cedera paling parah akan menjadi yang pertama dalam antrian.
Apa Karakteristik Antrian Prioritas?
Sebuah antrian disebut sebagai antrian prioritas jika memiliki karakteristik sebagai berikut:
- Setiap item memiliki beberapa prioritas yang terkait dengannya.
- Item dengan prioritas tertinggi dipindahkan di depan dan dihapus terlebih dahulu.
- Jika dua elemen berbagi nilai prioritas yang sama, maka antrian prioritas mengikuti prinsip masuk pertama keluar pertama untuk operasi de antrian.
Apa saja Jenis Antrian Prioritas?
Antrian prioritas terdiri dari dua jenis:
- Antrian Prioritas Urutan Ascending
- Antrian Prioritas Urutan Turun
Antrian Prioritas Urutan Ascending
Antrian prioritas urutan naik memberikan prioritas tertinggi ke nomor yang lebih rendah dalam antrian itu. Misalnya, Anda memiliki enam nomor dalam antrian prioritas yaitu 4, 8, 12, 45, 35, 20. Pertama, Anda akan mengatur angka-angka ini dalam urutan menaik. Daftar baru adalah sebagai berikut: 4, 8, 12, 20. 35, 45. Dalam daftar ini, 4 adalah angka terkecil. Oleh karena itu, antrian prioritas urutan menaik memperlakukan nomor 4 sebagai prioritas tertinggi.
| 4 | 8 | 12 | 20 | 35 | 45 |
Pada tabel di atas, 4 memiliki prioritas tertinggi, dan 45 memiliki prioritas terendah.
Antrian Prioritas Urutan Turun
Sebuah antrian prioritas urutan menurun memberikan prioritas tertinggi ke nomor tertinggi dalam antrian itu. Misalnya, Anda memiliki enam nomor dalam antrian prioritas yaitu 4, 8, 12, 45, 35, 20. Pertama, Anda akan mengatur angka-angka ini dalam urutan menaik. Daftar baru adalah sebagai berikut: 45, 35, 20, 12, 8, 4. Dalam daftar ini, 45 adalah angka tertinggi. Oleh karena itu, antrian prioritas urutan menurun memperlakukan nomor 45 sebagai prioritas tertinggi.
| 45 | 35 | 20 | 12 | 8 | 4 |
Pada tabel di atas, 4 memiliki prioritas terendah, dan 45 memiliki prioritas tertinggi.
Implementasi Antrian Prioritas dalam Struktur Data
Anda dapat menerapkan antrian prioritas dengan salah satu cara berikut:
- Daftar tertaut
- tumpukan biner
- Array
- Pohon pencarian biner
Tumpukan biner adalah metode yang paling efisien untuk mengimplementasikan antrian prioritas dalam struktur data .
Tabel di bawah ini merangkum kompleksitas operasi yang berbeda dalam antrian prioritas.
| Operasi | Array Tidak Terurut | Array yang Dipesan | Tumpukan Biner | Pohon Pencarian Biner |
| Memasukkan | 0(1) | 0(N) | 0(log(N)) | 0(log(N)) |
| Mengintip | 0(N) | 0(1) | 0(1) | 0(1) |
| Menghapus | 0(N) | 0(1) | 0(log (N)) | 0(log(N)) |
Tumpukan Biner
Pohon tumpukan biner mengatur semua simpul induk dan anak dari pohon dalam urutan tertentu. Dalam pohon tumpukan biner, simpul induk dapat memiliki maksimal 2 simpul anak. Nilai dari simpul induk dapat berupa:
- sama dengan atau kurang dari nilai simpul anak.
- sama dengan atau lebih dari nilai simpul anak.
Proses di atas membagi biner heap menjadi dua jenis: max heap dan min-heap.
Tumpukan Maks
Max heap adalah tumpukan biner di mana simpul induk memiliki nilai sama dengan atau lebih besar dari nilai simpul anak. Node akar pohon memiliki nilai tertinggi.
Memasukkan Elemen dalam Pohon Biner Tumpukan Maks
Anda dapat melakukan langkah-langkah berikut untuk menyisipkan elemen/angka dalam antrian prioritas dalam struktur data .
- Algoritma memindai pohon dari atas ke bawah dan kiri ke kanan untuk menemukan slot kosong. Kemudian memasukkan elemen pada simpul terakhir di pohon.
- Setelah memasukkan elemen, urutan pohon biner terganggu. Anda harus menukar data satu sama lain untuk mengurutkan urutan pohon biner tumpukan maksimum. Anda harus terus mengacak data sampai pohon memenuhi properti max-heap.
Algoritma untuk Menyisipkan Elemen dalam Pohon Biner Tumpukan Maks
Jika pohon kosong dan tidak mengandung simpul,
buat simpul induk baru newElement.
lain (simpul induk sudah tersedia)
masukkan newElement di akhir pohon (yaitu, simpul terakhir pohon dari kiri ke kanan.)
max-heapify pohon
Menghapus Elemen di Pohon Biner Tumpukan Maks
- Anda dapat melakukan langkah-langkah berikut untuk menghapus elemen dalam Antrian Prioritas di Struktur Data .
- Pilih elemen yang ingin Anda hapus dari pohon biner.
- Pergeseran data di akhir pohon dengan menukarnya dengan data simpul terakhir.
- Hapus elemen terakhir dari pohon biner.
- Setelah menghapus elemen, urutan pohon biner terganggu. Anda harus mengurutkan urutan untuk memenuhi properti max-heap. Anda harus terus mengacak data hingga pohon memenuhi properti max-heap.
Algoritma untuk Menghapus Elemen di Pohon Biner Tumpukan Maks
Jika elementUpForDeletion adalah LastNode,
hapus elemenUpForDeletion
lain ganti elementUpForDeletion dengan lastNode
hapus elemenUpForDeletion
max-heapify pohon
Temukan Elemen Maksimum atau Minimum dalam Pohon Biner Tumpukan Maks
Dalam pohon biner tumpukan maksimum, operasi find mengembalikan simpul induk (elemen tertinggi) dari pohon.
Algoritma untuk Menemukan Maks atau Min dalam Pohon Biner Tumpukan Maks
kembali ParentNode
Implementasi Program Priority Queue menggunakan Max Heap Binary Tree
| #sertakan <stdio.h> int binary_tree = 10; int max_heap = 0; tes int const = 100000;
batalkan swap( int *x, int *y ) { dalam sebuah; a = *x; *x= *y; *y = a; }
//Kode untuk menemukan induk di pohon tumpukan maksimum int findParentNode(int node[], int root) { if ((root > 1) && (root < binary_tree)) { kembali akar/2; } kembali -1; }
void max_heapify(int node[], int root) { int leftNodeRoot = findLeftChild(simpul, akar); int rightNodeRoot = findRightChild(simpul, akar);
// menemukan tertinggi di antara root, anak kiri dan anak kanan int tertinggi = akar;
if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) { if (simpul[kiriNodeRoot] > simpul[tertinggi]) { tertinggi = leftNodeRoot; } }
if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) { if (simpul[kananNodeRoot] > simpul[tertinggi]) { tertinggi = rightNodeRoot; } }
if (tertinggi != root) { swap(&simpul[akar], &simpul[tertinggi]); max_heapify(simpul, tertinggi); } }
void create_max_heap(int node[]) { int d; untuk(d=max_heap/2; d>=1; d–) { max_heapify(simpul, d); } }
int maksimum(int simpul[]) { kembali simpul[1]; }
int find_max(int simpul[]) { int maxNode = simpul[1]; simpul[1] = simpul[max_heap]; max_heap–; max_heapify(simpul, 1); kembali maxNode; } void descend_key(int node[], int node, int key) { A[akar] = kunci; max_heapify(simpul, akar); } void peningkatan_key(int node[], int root, int key) { simpul[akar] = kunci; while((root>1) && (simpul[findParentNode(simpul, root)] < simpul[root])) { swap(&node[root], &node[findParentNode(node, root)]); root = findParentNode(simpul, akar); } }
void insert(int node[], kunci int) { max_heap++; simpul[max_heap] = -1*tes; peningkatan_kunci(simpul, max_heap, kunci); }
void display_heap(int node[]) { int d; untuk(d=1; d<=max_heap; d++) { printf(“%d\n”,simpul[d]); } printf(“\n”); }
int utama() { int simpul[binary_tree]; masukkan(simpul, 10); masukkan(simpul, 4); masukkan(simpul, 20); masukkan(simpul, 50); masukkan(simpul, 1); masukkan(simpul, 15);
display_heap(simpul);
printf(“%d\n\n”, maksimum(simpul)); display_heap(simpul);
printf(“%d\n”, ekstrak_maks(simpul)); printf(“%d\n”, ekstrak_maks(simpul)); kembali 0; } |
Min Heap
Min-heap adalah tumpukan biner di mana simpul induk memiliki nilai yang sama atau lebih kecil dari nilai simpul anak. Node akar pohon memiliki nilai terendah.
Anda dapat mengimplementasikan min-heap dengan cara yang sama seperti max-heap kecuali membalik urutannya.
Kesimpulan
Contoh yang diberikan dalam artikel hanya untuk tujuan penjelasan. Anda dapat mengubah pernyataan yang diberikan di atas sesuai kebutuhan Anda. Di blog ini, kita belajar tentang konsep antrian prioritas dalam struktur data . Anda dapat mencoba contoh untuk memperkuat pengetahuan struktur data Anda.
Jika Anda penasaran untuk belajar tentang ilmu data, lihat Program PG Eksekutif 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.
Pelajari kursus ilmu data online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.
Antrian prioritas adalah antrian khusus dimana elemen-elemen dimasukkan berdasarkan prioritasnya. Fitur ini berguna dalam implementasi berbagai struktur data lainnya. Berikut ini adalah beberapa aplikasi antrian prioritas yang paling populer: Pendekatan yang digunakan dalam implementasi antrian prioritas menggunakan array adalah sederhana. Struktur dibuat untuk menyimpan nilai dan prioritas elemen dan kemudian larik dari struktur tersebut dibuat untuk menyimpan elemen. Operasi berikut terlibat dalam implementasi ini: Berikut ini mengilustrasikan perbedaan antara max heap dan min-heap.Apa aplikasi dari antrian prioritas?
1. Algoritma Jalur Terpendek Dijkstra: Antrian prioritas dapat digunakan dalam algoritma Jalur Terpendek Dijkstra ketika graf disimpan dalam bentuk daftar ketetanggaan.
2. Algoritme Prim : Algoritme Prim menggunakan antrian prioritas ke nilai-nilai atau kunci-kunci node dan menarik nilai-nilai minimum ini pada setiap langkah.
Kompresi Data : Kode Huffman menggunakan antrian prioritas untuk mengompresi data.
Sistem Operasi: Antrian prioritas sangat berguna untuk sistem operasi dalam berbagai proses seperti penyeimbangan beban dan penanganan gangguan. Pendekatan apa yang digunakan dalam implementasi antrian prioritas menggunakan array?
1. enqueue()-Fungsi ini menyisipkan elemen di akhir antrian.
2. peek() - Fungsi ini akan melintasi array untuk mengembalikan elemen dengan prioritas tertinggi. Jika menemukan dua elemen memiliki prioritas yang sama, ia mengembalikan elemen nilai tertinggi di antara mereka.
3. dequeue() - Fungsi ini akan menggeser semua elemen, 1 posisi ke kiri elemen dikembalikan oleh fungsi peek() dan memperkecil ukurannya. Apa perbedaan antara tumpukan maksimum dan tumpukan minimum?
Min Heap - Dalam min-heap, kunci dari simpul akar harus kurang dari atau sama dengan kunci dari simpul anak-anaknya. Ini menggunakan prioritas menaik. Node dengan kunci terkecil adalah prioritas. Elemen terkecil muncul sebelum elemen lainnya.
Max Heap - Dalam max heap, kunci dari simpul akar harus lebih besar dari atau sama dengan kunci dari simpul anak-anaknya. Ini menggunakan prioritas menurun. Node dengan kunci terbesar adalah prioritas. Elemen terbesar muncul sebelum elemen lainnya.