Rumah > Artikel > pembangunan bahagian belakang > 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:
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) Buat timbunan
Sebelum mencipta timbunan, anda perlu mencipta tatasusunan jenis vektor untuk menyimpan nombor yang hendak diisih:
vektor
Kemudian, kita boleh menggunakan fungsi make_heap untuk menukar tatasusunan jenis vektor kepada timbunan:
make_heap(v.begin(), v.end (), greater< ;int>());
Antaranya, greater
(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();
(1 ) Cipta timbunan
Tidak seperti kelas timbunan, kelas priority_queue boleh menentukan jenis timbunan apabila mengisytiharkan objek, seperti berikut:
priority_queue
(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.push (4);
q .push(1);q.push(9);
coutAtas ialah kandungan terperinci Timbunan dan baris gilir keutamaan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!