ในการใช้ C++priority_queue โปรแกรมควรเริ่มต้นด้วยรหัสเช่น:
#รวม
#รวม
โดยใช้ เนมสเปซชั่วโมง;
รวมถึงไลบรารีคิวในโปรแกรม
เพื่ออ่านต่อ ผู้อ่านควรมีความรู้พื้นฐานเกี่ยวกับ C++
เนื้อหาบทความ
- การก่อสร้างขั้นพื้นฐาน
- หน้าที่สำคัญของสมาชิก
- ฟังก์ชันคิวลำดับความสำคัญอื่นๆ
- ข้อมูลสตริง
- การก่อสร้างคิวลำดับความสำคัญอื่นๆ
- บทสรุป
การก่อสร้างขั้นพื้นฐาน
ต้องสร้างโครงสร้างข้อมูลก่อนจึงจะสามารถใช้งานได้ การสร้างที่นี่หมายถึงการสร้างอินสแตนซ์อ็อบเจ็กต์จากคลาสคิวของไลบรารี อ็อบเจ็กต์คิวต้องมีชื่อที่กำหนดโดยโปรแกรมเมอร์ ไวยากรณ์ที่ง่ายที่สุดในการสร้างลำดับความสำคัญคือ:
Priority_queue<พิมพ์>ชื่อคิว;
ด้วยไวยากรณ์นี้ ค่าที่มากที่สุดจะถูกลบออกก่อน ตัวอย่างของการสร้างอินสแตนซ์คือ:
Priority_queue<int>pq;หรือ
Priority_queue<char>pq;
เวกเตอร์และ deque เป็นโครงสร้างข้อมูลสองโครงสร้างใน C ++ สามารถสร้าง Priority_queue กับรายการใดรายการหนึ่งได้ ไวยากรณ์ในการสร้างคิวลำดับความสำคัญจากโครงสร้างเวกเตอร์คือ:
Priority_queue<พิมพ์เวกเตอร์<ประเภทเดียวกัน>, เปรียบเทียบ>pq;ตัวอย่างของการสร้างอินสแตนซ์นี้คือ:
Priority_queue<int, เวกเตอร์<int>, น้อย<int> >pq;สังเกตช่องว่างระหว่าง > และ > ที่ส่วนท้ายของการประกาศ ทั้งนี้เพื่อป้องกันความสับสนกับ >> รหัสเปรียบเทียบเริ่มต้นมีค่าน้อยกว่า หมายความว่าค่าที่ยิ่งใหญ่ที่สุดและไม่จำเป็นต้องเป็นค่าแรกจะถูกลบออกก่อน ดังนั้น คำสั่งการสร้างสามารถเขียนง่ายๆ ได้ดังนี้:
Priority_queue<int, เวกเตอร์<int> >pq;หากต้องลบค่าที่น้อยที่สุดก่อน คำสั่งจะต้องเป็น:
Priority_queue<int, เวกเตอร์<int>, มากกว่า<int> >pq;หน้าที่สำคัญของสมาชิก
ฟังก์ชัน push()
ฟังก์ชันนี้ส่งค่า ซึ่งเป็นอาร์กิวเมนต์ เข้าไปใน Priority_queue มันกลับเป็นโมฆะ รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
pq.ดัน(10);
pq.ดัน(30);
pq.ดัน(ยี่สิบ);
pq.ดัน(ห้าสิบ);
pq.ดัน(40);
Priority_queue นี้ได้รับค่าจำนวนเต็ม 5 ค่าตามลำดับ 10, 30, 20, 50, 40 หากองค์ประกอบทั้งหมดเหล่านี้ถูกดึงออกจากคิวลำดับความสำคัญ ค่าเหล่านั้นจะออกมาในลำดับที่ 50, 40, 30 20, 10.
ฟังก์ชัน pop()
ฟังก์ชันนี้จะลบค่าที่มีลำดับความสำคัญสูงสุดออกจาก Priority_queue หากโค้ดเปรียบเทียบมากกว่า ก็จะลบองค์ประกอบที่มีค่าน้อยที่สุดออก หากถูกเรียกอีกครั้ง มันจะลบองค์ประกอบถัดไปที่มีค่าน้อยที่สุดของส่วนที่เหลือ เรียกอีกครั้งจะลบค่าที่น้อยที่สุดถัดไปในปัจจุบันเป็นต้น มันกลับเป็นโมฆะ รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
pq.ดัน('ถึง');pq.ดัน('ค');pq.ดัน('NS');pq.ดัน('และ');pq.ดัน('NS');
โปรดทราบว่าในการเรียกใช้ฟังก์ชันสมาชิก ชื่อของอ็อบเจ็กต์จะต้องตามด้วยจุด ตามด้วยฟังก์ชัน
ฟังก์ชันด้านบน()
NS โผล่ () ฟังก์ชั่นลบค่าถัดไปของลำดับความสำคัญสูงสุด แต่ไม่ส่งคืนเป็น โผล่ () เป็นฟังก์ชันโมฆะ ใช้ สูงสุด() เพื่อให้ทราบถึงค่าของลำดับความสำคัญสูงสุดที่จะต้องเอาออกต่อไป NS สูงสุด() ฟังก์ชันส่งคืนสำเนาของค่าลำดับความสำคัญสูงสุดในpriority_queue รหัสต่อไปนี้ ซึ่งค่าถัดไปของลำดับความสำคัญสูงสุดคือค่าที่น้อยที่สุด แสดงสิ่งนี้
pq.ดัน('ถึง');pq.ดัน('ค');pq.ดัน('NS');pq.ดัน('และ');pq.ดัน('NS');
charch1=pq.สูงสุด();pq.โผล่();
charch2=pq.สูงสุด();pq.โผล่();
charch3=pq.สูงสุด();pq.โผล่();
charch4=pq.สูงสุด();pq.โผล่();
charch5=pq.สูงสุด();pq.โผล่();
ค่าใช้จ่าย<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<'NS';
ผลลัพธ์คือ 'a' 'b' 'c' 'd' 'e'
ฟังก์ชันที่ว่างเปล่า()
หากโปรแกรมเมอร์ใช้ สูงสุด() ทำงานบน priority_queue ที่ว่างเปล่า หลังจากคอมไพล์สำเร็จ เขาจะได้รับข้อความแสดงข้อผิดพลาดเช่น:
ดังนั้น ให้ตรวจสอบเสมอว่าคิวลำดับความสำคัญไม่ว่างก่อนใช้ สูงสุด() การทำงาน. NS ว่างเปล่า() ฟังก์ชันสมาชิกส่งคืนบูล จริง หากคิวว่างเปล่า และเป็นเท็จหากคิวไม่ว่างเปล่า รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
Priority_queue<int>pq;inti1= 10; inti2= 30; inti3= ยี่สิบ; inti4= ห้าสิบ; inti5= 40;
pq.ดัน(i1);pq.ดัน(i2);pq.ดัน(i3);pq.ดัน(i4);pq.ดัน(i5);
ในขณะที่(!pq.ว่างเปล่า())
{
ค่าใช้จ่าย <<pq.สูงสุด() << '';
pq.โผล่();
}
ค่าใช้จ่าย << 'NS';
ฟังก์ชันคิวลำดับความสำคัญอื่นๆ
ขนาด() ฟังก์ชั่น
ฟังก์ชันนี้จะคืนค่าความยาวของคิวลำดับความสำคัญ ดังที่แสดงในโค้ดต่อไปนี้:
inti1= 10; inti2= 30; inti3= ยี่สิบ; inti4= ห้าสิบ; inti5= 40;
pq.ดัน(i1);pq.ดัน(i2);pq.ดัน(i3);pq.ดัน(i4);pq.ดัน(i5);
intเลน=pq.ขนาด();
ค่าใช้จ่าย <<เลน<< 'NS';
ผลลัพธ์คือ 5
ฟังก์ชัน swap()
หาก Priority_queues สองรายการมีประเภทและขนาดเท่ากัน ฟังก์ชันนี้สามารถสลับกันได้ ดังที่แสดงในรหัสต่อไปนี้:
inti1= 10; inti2= 30; inti3= ยี่สิบ; inti4= ห้าสิบ; inti5= 40;
หน้า 1ดัน(i1);หน้า 1ดัน(i2);หน้า 1ดัน(i3);หน้า 1ดัน(i4);หน้า 1ดัน(i5);
Priority_queue<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
พีคิวเอดัน(it1);พีคิวเอดัน(it2);พีคิวเอดัน(it3);พีคิวเอดัน(it4);พีคิวเอดัน(it5);
หน้า 1แลกเปลี่ยน(pqA);
ในขณะที่(!หน้า 1ว่างเปล่า())
{
ค่าใช้จ่าย <<หน้า 1สูงสุด() << '';
หน้า 1โผล่();
} ค่าใช้จ่าย<<'NS';
ในขณะที่(!พีคิวเอว่างเปล่า())
{
ค่าใช้จ่าย <<พีคิวเอสูงสุด() << '';
พีคิวเอโผล่();
} ค่าใช้จ่าย<<'NS';
ผลลัพธ์คือ:
5 4 3 2 1
50 40 30 20 10
ดิเอ็มเพลส() Fuction
NS เอ็มเพลส() ฟังก์ชันจะคล้ายกับฟังก์ชันพุช รหัสต่อไปนี้แสดงให้เห็นสิ่งนี้:
inti1= 10; inti2= 30; inti3= ยี่สิบ; inti4= ห้าสิบ; inti5= 40;
หน้า 1เอ็มเพลส(i1);หน้า 1เอ็มเพลส(i2);หน้า 1เอ็มเพลส(i3);หน้า 1เอ็มเพลส(i4);หน้า 1เอ็มเพลส(i5);
ในขณะที่(!หน้า 1ว่างเปล่า())
{
ค่าใช้จ่าย <<หน้า 1สูงสุด() << '';
หน้า 1โผล่();
} ค่าใช้จ่าย<<'NS';
ผลลัพธ์คือ:
50 40 30 20 10
ข้อมูลสตริง
เมื่อเปรียบเทียบสตริง ควรใช้คลาสสตริง ไม่ใช่การใช้สตริงตามตัวอักษรโดยตรง เนื่องจากจะเปรียบเทียบพอยน์เตอร์และไม่ใช่สตริงจริง รหัสต่อไปนี้แสดงวิธีการใช้คลาสสตริง:
#รวมPriority_queue<สตริง>pq1;
สตริง s1=สตริง('ปากกา'), s2=สตริง('ดินสอ'), s3=สตริง('สมุดแบบฝึกหัด'), s4=สตริง('หนังสือเรียน'), s5=สตริง('ไม้บรรทัด');
หน้า 1ดัน(s1);หน้า 1ดัน(s2);หน้า 1ดัน(s3);หน้า 1ดัน(s4);หน้า 1ดัน(s5);
ในขณะที่(!หน้า 1ว่างเปล่า())
{
ค่าใช้จ่าย <<หน้า 1สูงสุด() << '';
หน้า 1โผล่();
} ค่าใช้จ่าย<<'NS';
ผลลัพธ์คือ:
ตำรา ไม้บรรทัด ดินสอ ปากกา หนังสือออกกำลังกาย
การก่อสร้างคิวลำดับความสำคัญอื่นๆ
การสร้างที่ชัดเจนจากเวกเตอร์
สามารถสร้างคิวลำดับความสำคัญได้อย่างชัดเจนจากเวกเตอร์ดังที่แสดงรหัสต่อไปนี้:
เวกเตอร์<int>vtr= {10,30,ยี่สิบ,ห้าสิบ,40};
Priority_queue<int>pq(วีทีอาร์เริ่ม(), วีทีอาร์จบ());
ในขณะที่(!pq.ว่างเปล่า())
{
ค่าใช้จ่าย <<pq.สูงสุด() << '';
pq.โผล่();
} ค่าใช้จ่าย<<'NS';
ผลลัพธ์คือ: 50 40 30 20 10 คราวนี้ ต้องรวมส่วนหัวของเวกเตอร์ด้วย อาร์กิวเมนต์สำหรับฟังก์ชันคอนสตรัคเตอร์ใช้จุดเริ่มต้นและจุดสิ้นสุดของเวกเตอร์ ชนิดข้อมูลสำหรับเวกเตอร์และชนิดข้อมูลสำหรับ Priority_queue จะต้องเหมือนกัน
ในการทำให้ลำดับความสำคัญมีค่าน้อยที่สุด การประกาศสำหรับตัวสร้างจะเป็น:
Priority_queue<int, เวกเตอร์<int>, มากกว่า>int> >pq(วีทีอาร์เริ่ม(), วีทีอาร์จบ()); การสร้างที่ชัดเจนจากอาร์เรย์
สามารถสร้างลำดับความสำคัญของคิวได้อย่างชัดเจนจากอาร์เรย์ดังแสดงรหัสต่อไปนี้:
Priority_queue<int>pq(อาร์ อาร์+5);
ในขณะที่(!pq.ว่างเปล่า())
{
ค่าใช้จ่าย <<pq.สูงสุด() << '';
pq.โผล่();
} ค่าใช้จ่าย<<'NS';
ผลลัพธ์คือ: 50 40 30 20 10 อาร์กิวเมนต์สำหรับฟังก์ชันคอนสตรัคเตอร์ใช้พอยน์เตอร์เริ่มต้นและสิ้นสุดของอาร์เรย์ arr ส่งกลับตัวชี้เริ่มต้น arr+5 ส่งกลับตัวชี้เมื่อผ่านอาร์เรย์ไป และ 5 คือขนาดของอาร์เรย์ ชนิดข้อมูลสำหรับอาร์เรย์และชนิดข้อมูลสำหรับpriority_queueต้องเหมือนกัน
ในการทำให้ลำดับความสำคัญมีค่าน้อยที่สุด การประกาศสำหรับตัวสร้างจะเป็น:
Priority_queue<int, เวกเตอร์<int>, มากกว่า<int> >pq(อาร์ อาร์+5);หมายเหตุ: ใน C++ ที่จริงpriority_queueจะเรียกว่าอะแด็ปเตอร์ ไม่ใช่แค่คอนเทนเนอร์
รหัสเปรียบเทียบแบบกำหนดเอง
การมีค่าทั้งหมดในคิวลำดับความสำคัญจากน้อยไปมากหรือมากไปหาน้อยทั้งหมดไม่ใช่ตัวเลือกเดียวสำหรับคิวลำดับความสำคัญ ตัวอย่างเช่น รายการของจำนวนเต็ม 11 สำหรับฮีปสูงสุดคือ:
88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69
ค่าสูงสุดคือ 88 ตามด้วยตัวเลขสองตัว: 86 และ 87 ซึ่งน้อยกว่า 88 ตัวเลขที่เหลือจะน้อยกว่าตัวเลขสามตัวนี้แต่ไม่เรียงตามลำดับ มีสองเซลล์ว่างในรายการ ตัวเลข 84 และ 82 น้อยกว่า 86 ตัวเลข 79 และ 74 น้อยกว่า 87 ตัวเลข 80 และ 81 น้อยกว่า 84 ตัวเลข 64 และ 69 น้อยกว่า 79
ตำแหน่งของตัวเลขเป็นไปตามเกณฑ์สูงสุด - ดูในภายหลัง ในการจัดเตรียมโครงร่างสำหรับ Priority_queue โปรแกรมเมอร์ต้องจัดเตรียมโค้ดเปรียบเทียบของตนเอง – ดูในภายหลัง
บทสรุป
C++priority_queue เป็นคิวเข้าก่อนออกก่อน ฟังก์ชั่นสมาชิก ดัน(), เพิ่มค่าใหม่ลงในคิว ฟังก์ชั่นสมาชิก สูงสุด(), อ่านค่าสูงสุดในคิว ฟังก์ชั่นสมาชิก โผล่ (), ลบโดยไม่คืนค่าสูงสุดของคิว ฟังก์ชั่นสมาชิก ว่างเปล่า(), ตรวจสอบว่าคิวว่างหรือไม่ อย่างไรก็ตาม Priority_queue แตกต่างจากคิว โดยจะเป็นไปตามอัลกอริธึมลำดับความสำคัญบางอย่าง มันอาจจะยิ่งใหญ่ที่สุด จากคนแรกไปคนสุดท้าย หรืออย่างน้อย จากคนแรกไปคนสุดท้าย เกณฑ์ (อัลกอริทึม) สามารถกำหนดโดยโปรแกรมเมอร์ได้เช่นกัน