Timbunan dan baris gilir keutamaan dalam C++

Timbunan dan baris gilir keutamaan ialah struktur data yang biasa digunakan dalam C++, dan kedua-duanya mempunyai nilai aplikasi yang penting. Artikel ini akan memperkenalkan dan menganalisis timbunan dan baris gilir keutamaan masing-masing untuk membantu pembaca memahami dan menggunakannya dengan lebih baik.

1. Heap

Heap ialah struktur data pokok khas yang boleh digunakan untuk melaksanakan baris gilir keutamaan. Dalam timbunan, setiap nod memenuhi sifat berikut:

1. Nilainya tidak kurang daripada (atau tidak lebih besar daripada) nilai nod induknya.
2. Subpokok kiri dan kanannya juga timbunan.

Kami memanggil timbunan yang tidak lebih kecil daripada nod induknya sebagai "timbunan min" dan timbunan yang tidak lebih besar daripada nod induknya sebagai "timbunan maks". Selain itu, timbunan biasanya merupakan pokok binari yang lengkap, iaitu, nod dalam tahap lain penuh kecuali untuk tahap terakhir, di mana nod disusun dari kiri ke kanan.

Dalam C++, perpustakaan STL menyediakan dua kelas, heap dan priority_queue, untuk melaksanakan heap. Antaranya, kelas heap menyediakan fungsi operasi heap, seperti make_heap, push_heap, pop_heap, dsb., dan kelas priority_queue ialah baris gilir keutamaan berdasarkan pelaksanaan heap. Seterusnya, mari kita lihat pada penggunaan heap dan priority_queue.

1. kelas timbunan

(1) Buat timbunan

Sebelum mencipta timbunan, anda perlu mencipta tatasusunan jenis vektor untuk menyimpan nombor yang hendak diisih:

vektor 4, 1, 5, 9, 2, 6, 5, 3 };

Kemudian, kita boleh menggunakan fungsi make_heap untuk menukar tatasusunan jenis vektor kepada timbunan:

make_heap(v.begin(), v.end (), greater< ;int>());

Antaranya, greater() mewakili fungsi perbandingan, yang boleh mengawal jenis timbunan.

(2) Masukkan elemen

Untuk memasukkan elemen ke dalam timbunan, anda boleh menggunakan fungsi push_heap Penggunaannya adalah seperti berikut:

v.push_back(7);
push_heap(v.begin(), v.end. (), greater());

(3) Padamkan elemen

Untuk memadamkan elemen daripada timbunan, anda boleh menggunakan fungsi pop_heap, yang akan mengalihkan elemen atas timbunan ke kedudukan terakhir timbunan dan padamkan elemen daripada timbunan. Penggunaan fungsi ini adalah seperti berikut:

pop_heap(v.begin(), v.end(), greater());
v.pop_back();

2. priority_queue class

(1 ) Cipta timbunan

Tidak seperti kelas timbunan, kelas priority_queue boleh menentukan jenis timbunan apabila mengisytiharkan objek, seperti berikut:

priority_queue, greater> q;

bermakna mencipta timbunan minimum.

(2) Masukkan elemen

Memasukkan elemen dalam priority_queue boleh terus menggunakan fungsi push, seperti yang ditunjukkan di bawah:

q.push(2); q.push(9);

(3) Padamkan elemen

Untuk memadamkan elemen dalam priority_queue, anda boleh terus menggunakan fungsi pop, seperti yang ditunjukkan di bawah:

q.pop();

2 Baris gilir keutamaan ialah Baris gilir khas yang menyusun elemen mengikut keutamaan, meletakkan elemen dengan keutamaan tertinggi di hadapan baris gilir dan elemen dengan keutamaan terendah pada penghujung baris gilir. Anda boleh menggunakan timbunan untuk melaksanakan baris gilir keutamaan.

Dalam C++, kelas priority_queue ialah baris gilir keutamaan yang dilaksanakan berdasarkan timbunan Ia boleh menggunakan fungsi dalam kelas timbunan dan priority_queue di atas untuk melaksanakan operasi pemasukan dan pemadaman elemen. Selain itu, fungsi teratas juga disediakan dalam kelas priority_queue, yang digunakan untuk mengakses elemen dengan keutamaan tertinggi, seperti yang ditunjukkan di bawah:

priority_queue q;

q.push(2);

q.push (4);

q .push(1);

q.push(9);

cout
Ringkasan:

timbunan dan keutamaan dalam Gilir C++, dan masing-masing menganalisis penggunaan dan prinsip pelaksanaan timbunan dan baris gilir keutamaan. Dengan mengkaji artikel ini, pembaca boleh lebih memahami kedua-dua struktur data ini dan menggunakannya secara fleksibel dalam pengaturcaraan sebenar. Pada masa yang sama, pembaca harus memberi perhatian kepada masa dan langkah berjaga-jaga untuk menggunakan timbunan dan baris gilir keutamaan untuk memastikan ketepatan dan kecekapan kod.

Atas ialah kandungan terperinci Timbunan dan baris gilir keutamaan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!