Bagaimana cara menggunakan C++ Priority_queue?

How Use C Priority_queue

Dalam C++, antrian adalah struktur data daftar di mana elemen pertama yang dimasukkan ke dalam daftar adalah elemen pertama yang dihapus, saat penghapusan akan dilakukan. Antrian prioritas dalam C++ serupa, tetapi memiliki beberapa urutan; itu adalah elemen dengan nilai terbesar yang dihilangkan terlebih dahulu. Antrian prioritas masih dapat dikonfigurasi sehingga elemen dengan nilai terkecil yang dihapus terlebih dahulu. Setiap antrian harus memiliki setidaknya dorongan() fungsi dan pop () fungsi. NS dorongan() fungsi menambahkan elemen baru di belakang. Untuk antrian normal, pop () fungsi menghapus elemen pertama yang pernah dimasukkan. Untuk antrian prioritas, pop () fungsi menghapus elemen dengan prioritas tertinggi, yang bisa menjadi yang terbesar atau terkecil, tergantung pada skema pemesanan.

Untuk menggunakan C++ priority_queue, program harus dimulai dengan kode seperti:



#termasuk
#termasuk
menggunakan ruang namajam;

Ini termasuk perpustakaan antrian ke dalam program.



Untuk melanjutkan membaca, pembaca harus memiliki pengetahuan dasar tentang C++.



Isi Artikel

Konstruksi Dasar

Struktur data harus dibangun terlebih dahulu sebelum dapat digunakan. Konstruksi di sini berarti membuat instance objek dari kelas antrian perpustakaan. Objek antrian kemudian harus memiliki nama yang diberikan oleh programmer. Sintaks paling sederhana untuk membuat antrian prioritas adalah:

prioritas_antrian<Tipe>nama antrian;

Dengan sintaks ini, nilai terbesar dihilangkan terlebih dahulu. Contoh Instansiasi adalah :

prioritas_antrian<ke dalam>pq;

atau



prioritas_antrian<arang>pq;

Vektor dan deque adalah dua struktur data dalam C++. Prioritas_antrian dapat dibuat dengan salah satu dari mereka. Sintaks untuk membuat antrian prioritas dari struktur vektor adalah:

prioritas_antrian<jenis, vektor<Tipe yang sama>, membandingkan>pq;

Contoh dari instantiasi ini adalah:

prioritas_antrian<ke dalam, vektor<ke dalam>, lebih sedikit<ke dalam> >pq;

Perhatikan jarak antara > dan > di akhir deklarasi. Ini untuk mencegah kebingungan dengan >>. Kode perbandingan default lebih kecil, artinya nilai terbesar, dan belum tentu nilai pertama, akan dihapus terlebih dahulu. Jadi, pernyataan penciptaan secara sederhana dapat ditulis sebagai:

prioritas_antrian<ke dalam, vektor<ke dalam> >pq;

Jika nilai terkecil harus dihilangkan terlebih dahulu, maka pernyataannya harus:

prioritas_antrian<ke dalam, vektor<ke dalam>, lebih besar<ke dalam> >pq;

Fungsi Anggota Penting

Fungsi push()
Fungsi ini mendorong nilai, yang merupakan argumennya, ke dalam priority_queue. Ia kembali batal. Kode berikut menggambarkan hal ini:

prioritas_antrian<ke dalam>pq;

hal.dorongan(10);
hal.dorongan(30);
hal.dorongan(dua puluh);
hal.dorongan(lima puluh);
hal.dorongan(40);

Priority_queue ini telah menerima 5 nilai integer dalam urutan 10, 30, 20, 50, 40. Jika semua elemen ini harus dikeluarkan dari antrian prioritas, maka mereka akan keluar dalam urutan 50, 40, 30, 20, 10.

Fungsi pop()
Fungsi ini menghapus dari priority_queue nilai dengan prioritas tertinggi. Jika kode perbandingan lebih besar, maka akan menghapus elemen dengan nilai terkecil. Jika dipanggil lagi, ia menghapus elemen berikutnya dengan nilai terkecil dari sisanya; dipanggil lagi, itu menghilangkan nilai terkecil berikutnya yang ada, dan seterusnya. Ia kembali batal. Kode berikut menggambarkan hal ini:

prioritas_antrian<arang, vektor<arang>, lebih besar<ke dalam> >pq;
hal.dorongan('ke');hal.dorongan('C');hal.dorongan('B');hal.dorongan('Dan');hal.dorongan('D');

Perhatikan bahwa untuk memanggil fungsi anggota, nama objek harus diikuti oleh titik, lalu fungsi.

Fungsi atas ()
NS pop () fungsi menghapus nilai prioritas tertinggi berikutnya, tetapi tidak mengembalikannya, karena pop () adalah fungsi kosong. Menggunakan atas() berfungsi untuk mengetahui nilai prioritas tertinggi yang harus dihilangkan selanjutnya. NS atas() fungsi mengembalikan salinan nilai prioritas tertinggi di priority_queue. Kode berikut, di mana nilai prioritas tertinggi berikutnya adalah nilai terkecil, menggambarkan hal ini:

prioritas_antrian<arang, vektor<arang>, lebih besar<ke dalam> >pq;
hal.dorongan('ke');hal.dorongan('C');hal.dorongan('B');hal.dorongan('Dan');hal.dorongan('D');
arangch1=hal.atas();hal.pop();
arangch2=hal.atas();hal.pop();
arangch3=hal.atas();hal.pop();
arangch4=hal.atas();hal.pop();
arangch5=hal.atas();hal.pop();

biaya<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';

Outputnya adalah 'a' 'b' 'c' 'd' 'e'.

Fungsi kosong()
Jika seorang programmer menggunakan atas() berfungsi pada priority_queue yang kosong, setelah kompilasi berhasil, ia akan menerima pesan kesalahan seperti:

Kesalahan segmentasi(inti dibuang)

Jadi, selalu periksa apakah antrian prioritas tidak kosong sebelum menggunakan atas() fungsi. NS kosong() fungsi anggota mengembalikan bool, true, jika antrian kosong, dan false jika antrian tidak kosong. Kode berikut menggambarkan hal ini:

prioritas_antrian<ke dalam>pq;
ke dalami1= 10; ke dalami2= 30; ke dalami3= dua puluh; ke dalami4= lima puluh; ke dalami5= 40;
hal.dorongan(i1);hal.dorongan(i2);hal.dorongan(i3);hal.dorongan(i4);hal.dorongan(i5);

ketika(!hal.kosong())
{
biaya <<hal.atas() << '';
hal.pop();
}
biaya << ' ';

Fungsi Antrian Prioritas Lainnya

Ukuran() Fungsi
Fungsi ini mengembalikan panjang antrian prioritas, seperti yang diilustrasikan oleh kode berikut:

prioritas_antrian<ke dalam>pq;
ke dalami1= 10; ke dalami2= 30; ke dalami3= dua puluh; ke dalami4= lima puluh; ke dalami5= 40;
hal.dorongan(i1);hal.dorongan(i2);hal.dorongan(i3);hal.dorongan(i4);hal.dorongan(i5);

ke dalamlen=hal.ukuran();
biaya <<len<< ' ';

Keluarannya adalah 5.

Fungsi swap()
Jika dua priority_queues memiliki tipe dan ukuran yang sama, maka keduanya dapat ditukar dengan fungsi ini, seperti yang ditunjukkan oleh kode berikut:

prioritas_antrian<ke dalam>pq1;
ke dalami1= 10; ke dalami2= 30; ke dalami3= dua puluh; ke dalami4= lima puluh; ke dalami5= 40;
pq1.dorongan(i1);pq1.dorongan(i2);pq1.dorongan(i3);pq1.dorongan(i4);pq1.dorongan(i5);

prioritas_antrian<ke dalam>pqA;
ke dalamitu1= 1; ke dalamitu2= 3; ke dalamitu3= 2; ke dalamitu4= 5; ke dalamitu5= 4;
pqA.dorongan(itu1);pqA.dorongan(itu2);pqA.dorongan(itu3);pqA.dorongan(itu4);pqA.dorongan(itu5);

pq1.menukar(pqA);

ketika(!pq1.kosong())
{
biaya <<pq1.atas() << '';
pq1.pop();
} biaya<<' ';

ketika(!pqA.kosong())
{
biaya <<pqA.atas() << '';
pqA.pop();
} biaya<<' ';

Outputnya adalah:

 5  4  3  2  1
 50  40  30  20 ​​ 10

Emplase() Fungsi
NS menempatkan() fungsinya mirip dengan fungsi push. Kode berikut menggambarkan hal ini:

prioritas_antrian<ke dalam>pq1;
ke dalami1= 10; ke dalami2= 30; ke dalami3= dua puluh; ke dalami4= lima puluh; ke dalami5= 40;
pq1.menempatkan(i1);pq1.menempatkan(i2);pq1.menempatkan(i3);pq1.menempatkan(i4);pq1.menempatkan(i5);

ketika(!pq1.kosong())
{
biaya <<pq1.atas() << '';
pq1.pop();
} biaya<<' ';

Outputnya adalah:

50 40 30 20 10

String Data

Saat membandingkan string, kelas string harus digunakan dan bukan penggunaan langsung literal string karena akan membandingkan pointer dan bukan string yang sebenarnya. Kode berikut menunjukkan bagaimana kelas string digunakan:

#termasuk
prioritas_antrian<rangkaian>pq1;
senar s1=rangkaian('pena'), s2=rangkaian('pensil'), s3=rangkaian('buku latihan'), s4=rangkaian('buku teks'), s5=rangkaian('penggaris');

pq1.dorongan(s1);pq1.dorongan(s2);pq1.dorongan(s3);pq1.dorongan(s4);pq1.dorongan(s5);
ketika(!pq1.kosong())
{
biaya <<pq1.atas() << '';
pq1.pop();
} biaya<<' ';

Outputnya adalah:

 buku teks  penggaris  pensil  pena  buku latihan

Konstruksi Antrian Prioritas Lainnya

Penciptaan Eksplisit dari Vektor
Antrian prioritas dapat dibuat secara eksplisit dari vektor seperti yang ditunjukkan oleh kode berikut:

#termasuk
vektor<ke dalam>vtr= {10,30,dua puluh,lima puluh,40};

prioritas_antrian<ke dalam>pq(vtr.mulai(), vtr.akhir());

ketika(!hal.kosong())
{
biaya <<hal.atas() << '';
hal.pop();
} biaya<<' ';

Outputnya adalah: 50 40 30 20 10. Kali ini, header vektor juga harus disertakan. Argumen untuk fungsi konstruktor mengambil pointer awal dan akhir dari vektor. Tipe data untuk vektor dan tipe data untuk priority_queue harus sama.

Untuk menjadikan nilai terkecil sebagai prioritas, deklarasi untuk konstruktor adalah:

prioritas_antrian<ke dalam, vektor<ke dalam>, lebih besar>ke dalam> >pq(vtr.mulai(), vtr.akhir());

Penciptaan Eksplisit dari Array
Antrian prioritas dapat dibuat secara eksplisit dari array seperti yang ditunjukkan oleh kode berikut:

ke dalamarr[] = {10,30,dua puluh,lima puluh,40};

prioritas_antrian<ke dalam>pq(arr, arr+5);

ketika(!hal.kosong())
{
biaya <<hal.atas() << '';
hal.pop();
} biaya<<' ';

Outputnya adalah: 50 40 30 20 10. Argumen untuk fungsi konstruktor mengambil pointer awal dan akhir dari array. arr mengembalikan pointer awal, arr+5 mengembalikan pointer yang melewati array, dan 5 adalah ukuran array. Tipe data untuk array dan tipe data untuk priority_queue harus sama.

Untuk menjadikan nilai terkecil sebagai prioritas, deklarasi untuk konstruktor adalah:

prioritas_antrian<ke dalam, vektor<ke dalam>, lebih besar<ke dalam> >pq(arr, arr+5);

Catatan: Dalam C++, priority_queue sebenarnya disebut adaptor, bukan hanya wadah.

Kode Bandingkan Kustom

Memiliki semua nilai dalam antrian prioritas naik atau semua turun bukanlah satu-satunya pilihan untuk antrian prioritas. Misalnya, daftar 11 bilangan bulat untuk tumpukan maksimum adalah:

88, 86, 87, 84, 82, 79,74, 80, 81,, 64, 69

Nilai tertinggi adalah 88. Ini diikuti oleh dua angka: 86 dan 87, yang kurang dari 88. Angka-angka lainnya kurang dari tiga angka ini, tetapi tidak benar-benar berurutan. Ada dua sel kosong dalam daftar. Angka 84 dan 82 kurang dari 86. Angka 79 dan 74 kurang dari 87. Angka 80 dan 81 lebih kecil dari 84. Angka 64 dan 69 kurang dari 79.

Penempatan angka mengikuti kriteria max-heap – lihat nanti. Untuk menyediakan skema seperti itu untuk priority_queue, programmer harus menyediakan kode perbandingannya sendiri – lihat nanti.

Kesimpulan

A C++ priority_queue adalah antrian masuk pertama keluar pertama. fungsi anggota, dorongan(), menambahkan nilai baru ke dalam antrian. fungsi anggota, atas(), membaca nilai teratas dalam antrian. fungsi anggota, pop(), menghapus tanpa mengembalikan nilai teratas antrian. fungsi anggota, kosong(), memeriksa apakah antrian kosong. Namun, priority_queue berbeda dari antrian, dalam hal itu, mengikuti beberapa algoritma prioritas. Itu bisa menjadi yang terbesar, dari pertama hingga terakhir, atau paling tidak, dari pertama hingga terakhir. Kriteria (algoritma) juga dapat ditentukan oleh pemrogram.