คิวลำดับความสำคัญในโครงสร้างข้อมูล: ลักษณะ, ประเภท & การนำไปใช้

เผยแพร่แล้ว: 2021-05-02

สารบัญ

บทนำ

คิวลำดับความสำคัญใน โครงสร้าง ข้อมูล เป็นส่วนขยายของคิว "ปกติ" เป็นชนิดข้อมูลนามธรรมที่มีกลุ่มของรายการ มันเหมือนกับคิว "ปกติ" ยกเว้นว่าองค์ประกอบการดีคิวจะเป็นไปตามลำดับความสำคัญ ลำดับความสำคัญจะยกเลิกรายการเหล่านั้นก่อนที่มีลำดับความสำคัญสูงสุด บล็อกนี้จะช่วยให้คุณเข้าใจลึกซึ้งยิ่งขึ้นเกี่ยวกับลำดับความสำคัญและการนำไปใช้ในภาษาซี

คิวลำดับความสำคัญคืออะไร

เป็นชนิดข้อมูลนามธรรมที่ให้วิธีการรักษาชุดข้อมูล คิว "ปกติ" ตามรูปแบบการเข้าก่อนออกก่อน มัน dequeues องค์ประกอบในลำดับเดียวกันตามในขณะที่ดำเนินการแทรก อย่างไรก็ตาม ลำดับองค์ประกอบในคิวลำดับความสำคัญขึ้นอยู่กับลำดับความสำคัญขององค์ประกอบในคิวนั้น คิวลำดับความสำคัญจะย้ายองค์ประกอบที่มีลำดับความสำคัญสูงสุดที่จุดเริ่มต้นของคิวที่มีลำดับความสำคัญและองค์ประกอบที่มีลำดับความสำคัญต่ำสุดที่ด้านหลังของคิวที่มีลำดับความสำคัญ

รองรับเฉพาะองค์ประกอบที่เปรียบเทียบได้ ดังนั้น คิวลำดับความสำคัญใน โครงสร้างข้อมูลจะ จัดเรียงองค์ประกอบตามลำดับจากน้อยไปมากหรือจากมากไปน้อย

คุณสามารถนึกถึงคิวลำดับความสำคัญได้เนื่องจากผู้ป่วยหลายรายรอเข้าแถวที่โรงพยาบาล ที่นี่ สถานการณ์ของผู้ป่วยกำหนดลำดับความสำคัญ ผู้ป่วยที่มีอาการบาดเจ็บรุนแรงที่สุดจะเป็นคิวแรก

ลักษณะของคิวลำดับความสำคัญคืออะไร

คิวจะเรียกว่าคิวลำดับความสำคัญหากมีลักษณะดังต่อไปนี้:

  • แต่ละรายการมีลำดับความสำคัญบางอย่างที่เกี่ยวข้อง
  • รายการที่มีลำดับความสำคัญสูงสุดจะถูกย้ายไปที่ด้านหน้าและลบออกก่อน
  • หากองค์ประกอบสองรายการมีค่าลำดับความสำคัญเท่ากัน คิวลำดับความสำคัญจะเป็นไปตามหลักการเข้าก่อน-ออกก่อนสำหรับการดำเนินการคิว

คิวลำดับความสำคัญมีกี่ประเภท

คิวลำดับความสำคัญมีสองประเภท:

  • คิวลำดับความสำคัญจากน้อยไปมาก
  • คิวลำดับความสำคัญของคำสั่งซื้อจากมากไปน้อย

คิวลำดับความสำคัญจากน้อยไปมาก

คิวลำดับความสำคัญของลำดับจากน้อยไปมากจะให้ความสำคัญสูงสุดกับจำนวนที่ต่ำกว่าในคิวนั้น ตัวอย่างเช่น คุณมีตัวเลขหกตัวในคิวลำดับความสำคัญที่ 4, 8, 12, 45, 35, 20 อันดับแรก คุณจะจัดเรียงตัวเลขเหล่านี้ในลำดับจากน้อยไปมาก รายการใหม่มีดังนี้ 4, 8, 12, 20. 35, 45. ในรายการนี้ 4 เป็นตัวเลขที่น้อยที่สุด ดังนั้น ลำดับความสำคัญของลำดับจากน้อยไปมากจึงถือว่าหมายเลข 4 เป็นลำดับความสำคัญสูงสุด

4 8 12 20 35 45

ใน ตารางด้านบน 4 มีลำดับความสำคัญสูงสุด และ 45 มีลำดับความสำคัญต่ำสุด

คิวลำดับความสำคัญของคำสั่งซื้อจากมากไปน้อย

คิวลำดับความสำคัญของลำดับจากมากไปน้อยจะให้ความสำคัญสูงสุดกับจำนวนสูงสุดในคิวนั้น ตัวอย่างเช่น คุณมีตัวเลขหกตัวในคิวลำดับความสำคัญที่ 4, 8, 12, 45, 35, 20 อันดับแรก คุณจะจัดเรียงตัวเลขเหล่านี้ในลำดับจากน้อยไปมาก รายการใหม่มีดังนี้ 45, 35, 20, 12, 8, 4. ในรายการนี้ 45 เป็นจำนวนสูงสุด ดังนั้น คิวลำดับความสำคัญของลำดับจากมากไปน้อยถือว่าหมายเลข 45 เป็นลำดับความสำคัญสูงสุด

45 35 20 12 8 4

ในตารางด้านบน 4 มีลำดับความสำคัญต่ำสุด และ 45 มีลำดับความสำคัญสูงสุด

การนำคิวลำดับความสำคัญไปใช้ในโครงสร้างข้อมูล

คุณสามารถใช้คิวลำดับความสำคัญด้วยวิธีใดวิธีหนึ่งต่อไปนี้:

  • รายการเชื่อมโยง
  • ฮีปไบนารี
  • อาร์เรย์
  • ต้นไม้ค้นหาไบนารี

ฮีปไบนารีเป็นวิธีที่มีประสิทธิภาพสูงสุดสำหรับการนำ ลำดับความสำคัญไปใช้ใน โครงสร้าง ข้อมูล

ตารางด้านล่างสรุปความซับซ้อนของการดำเนินการต่างๆ ในคิวที่มีลำดับความสำคัญ

การดำเนินการ Unordered Array อาร์เรย์ที่สั่งซื้อ กองไบนารี แผนผังการค้นหาไบนารี
แทรก 0(1) 0(N) 0(บันทึก(N)) 0(บันทึก(N))
แอบมอง 0(N) 0(1) 0(1) 0(1)
ลบ 0(N) 0(1) 0(บันทึก (N)) 0(บันทึก(N))

กองไบนารี

ไบนารีฮีปทรีจะจัดระเบียบโหนดหลักและโหนดย่อยของทรีตามลำดับเฉพาะ ในทรีไบนารีไบนารี โหนดหลักสามารถมีโหนดย่อยได้สูงสุด 2 โหนด ค่าของโหนดหลักอาจเป็น:

  • เท่ากับหรือน้อยกว่าค่าของโหนดย่อย
  • เท่ากับหรือมากกว่าค่าของโหนดย่อย

กระบวนการข้างต้นแบ่งไบนารีฮีปออกเป็นสองประเภท: max heap และ min-heap

Max Heap

ฮีปสูงสุดคือฮีปไบนารีที่โหนดหลักมีค่าเท่ากับหรือมากกว่าค่าโหนดย่อย โหนดรากของต้นไม้มีค่าสูงสุด

การแทรกองค์ประกอบใน Max Heap Binary Tree

คุณสามารถทำตามขั้นตอนต่อไปนี้เพื่อแทรกองค์ประกอบ/ตัวเลขใน คิวลำดับความสำคัญในโครงสร้าง ข้อมูล

  1. อัลกอริทึมจะสแกนต้นไม้จากบนลงล่างและจากซ้ายไปขวาเพื่อค้นหาช่องว่าง จากนั้นจะแทรกองค์ประกอบที่โหนดสุดท้ายในแผนผัง
  2. หลังจากแทรกองค์ประกอบแล้ว ลำดับของไบนารีทรีจะถูกรบกวน คุณต้องสลับข้อมูลระหว่างกันเพื่อจัดเรียงลำดับของต้นไม้ไบนารีฮีปสูงสุด คุณต้องสับเปลี่ยนข้อมูลต่อไปจนกว่าต้นไม้จะตรงตามคุณสมบัติ max-heap

อัลกอริธึมเพื่อแทรกองค์ประกอบใน Max Heap Binary Tree

หากต้นไม้ว่างเปล่าและไม่มีโหนด

สร้างโหนดหลักใหม่ newElement

อื่น ๆ (โหนดหลักมีอยู่แล้ว)

แทรกองค์ประกอบใหม่ที่ส่วนท้ายของทรี (เช่น โหนดสุดท้ายของทรีจากซ้ายไปขวา)

max-heapify ต้นไม้

การลบองค์ประกอบใน Max Heap Binary Tree

  1. คุณสามารถทำตามขั้นตอนต่อไปนี้เพื่อลบองค์ประกอบใน คิวลำดับความสำคัญในโครงสร้าง ข้อมูล
  2. เลือกองค์ประกอบที่คุณต้องการลบออกจากไบนารีทรี
  3. เลื่อนข้อมูลที่ส่วนท้ายของทรีโดยสลับกับข้อมูลโหนดสุดท้าย
  4. ลบองค์ประกอบสุดท้ายของไบนารีทรี
  5. หลังจากลบองค์ประกอบแล้ว ลำดับของไบนารีทรีจะถูกรบกวน คุณต้องเรียงลำดับเพื่อให้เป็นไปตามคุณสมบัติของ max-heap คุณต้องสับเปลี่ยนข้อมูลต่อไปจนกว่าต้นไม้จะตรงตามคุณสมบัติ max-heap

อัลกอริทึมการลบองค์ประกอบใน Max Heap Binary Tree

หาก elementUpForDeletion เป็น LastNode

ลบ elementUpForDeletion

อื่นแทนที่ elementUpForDeletion ด้วย lastNode

ลบ elementUpForDeletion

max-heapify ต้นไม้

ค้นหาองค์ประกอบสูงสุดหรือต่ำสุดในแผนภูมิไบนารีฮีปสูงสุด

ในทรีไบนารีฮีปสูงสุด การดำเนินการ find จะส่งคืนโหนดหลัก (องค์ประกอบสูงสุด) ของทรี

อัลกอริธึมเพื่อค้นหาค่าสูงสุดหรือต่ำสุดในแผนภูมิไบนารี Max Heap

ส่งคืน ParentNode

การใช้งานโปรแกรมของคิวลำดับความสำคัญโดยใช้ Max Heap Binary Tree

#include <stdio.h>

int binary_tree = 10;

int max_heap = 0;

การทดสอบ int const = 100000;

ถือเป็นโมฆะ swap (int *x, int *y ) {

int ก;

ก = *x;

*x= *y;

*y = ก;

}

//โค้ดสำหรับค้นหาพาเรนต์ใน max heap tree

int findParentNode (โหนด int [], รูท int) {

ถ้า ((ราก > 1) && (ราก < binary_tree)) {

ส่งคืนรูท/2;

}

กลับ -1;

}

เป็นโมฆะ max_heapify (โหนด int [], int root) {

int leftNodeRoot = findLeftChild (โหนด, รูท);

int rightNodeRoot = findRightChild (โหนด, รูท);

// ค้นหาสูงสุดระหว่างรูท ลูกซ้าย ลูกขวา

int สูงสุด = รูท;

ถ้า ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

ถ้า (โหนด [leftNodeRoot] > โหนด [สูงสุด]) {

สูงสุด = leftNodeRoot;

}

}

ถ้า ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

ถ้า (โหนด [rightNodeRoot] > โหนด [สูงสุด]) {

สูงสุด = rightNodeRoot;

}

}

ถ้า (สูงสุด != รูท) {

สลับ(&โหนด[รูท], &โหนด[สูงสุด]);

max_heapify(โหนด สูงสุด);

}

}

เป็นโมฆะ create_max_heap (โหนด int []) {

int d;

สำหรับ (d=max_heap/2; d>=1; d–) {

max_heapify (โหนด d);

}

}

int สูงสุด (โหนด int []) {

โหนดกลับ[1];

}

int find_max (โหนด int []) {

int maxNode = โหนด [1];

โหนด[1] = โหนด[max_heap];

max_heap–;

max_heapify (โหนด 1);

ส่งคืน maxNode;

}

เป็นโมฆะ descend_key (โหนด int [], โหนด int, คีย์ int) {

A[root] = คีย์;

max_heapify (โหนด, รูท);

}

เป็นโมฆะ added_key (โหนด int [], รูท int, คีย์ int) {

โหนด [รูท] = คีย์;

ในขณะที่ ((ราก> 1) && (โหนด [findParentNode (โหนด, รูท)] < โหนด [รูท])) {

สลับ(&โหนด[รูท], &โหนด[findParentNode(โหนด, รูท)]);

root = findParentNode(โหนด, รูท);

}

}

การแทรกเป็นโมฆะ (โหนด int [], คีย์ int) {

max_heap++;

โหนด[max_heap] = -1*ทดสอบ;

เพิ่ม_key(โหนด, max_heap, คีย์);

}

เป็นโมฆะ display_heap (โหนด int []) {

int d;

สำหรับ (d=1; d<=max_heap; d++) {

printf(“%d\n”,โหนด[d]);

}

printf(“\n”);

}

int หลัก () {

โหนด int [binary_tree];

แทรก(โหนด 10);

แทรก(โหนด 4);

แทรก(โหนด 20);

แทรก(โหนด 50);

แทรก(โหนด 1);

แทรก(โหนด 15);

display_heap(โหนด);

printf(“%d\n\n”, สูงสุด (โหนด));

display_heap(โหนด);

printf(“%d\n”, extract_max(โหนด));

printf(“%d\n”, extract_max(โหนด));

กลับ 0;

}

มิน ฮีป

min-heap เป็นไบนารีฮีปที่โหนดหลักมีค่าเท่ากับหรือน้อยกว่าค่าโหนดย่อย โหนดรากของต้นไม้มีค่าต่ำสุด

คุณสามารถใช้ min-heap ในลักษณะเดียวกับ max-heap ยกเว้นการย้อนกลับลำดับ

บทสรุป

ตัวอย่างที่ให้ไว้ในบทความมีจุดประสงค์เพื่ออธิบายเท่านั้น คุณสามารถแก้ไขข้อความที่ระบุข้างต้นได้ตามความต้องการของคุณ ในบล็อกนี้ เราได้เรียนรู้เกี่ยวกับแนวคิดของ ลำดับความสำคัญในโครงสร้าง ข้อมูล คุณสามารถลองใช้ตัวอย่างเพื่อเสริมสร้างความรู้ด้านโครงสร้างข้อมูลของคุณ

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ลองดูโปรแกรม Executive PG ของ IIIT-B & upGrad ใน Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1 -on-1 พร้อมที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

เรียนรู้ หลักสูตรวิทยาศาสตร์ข้อมูล ออนไลน์จากมหาวิทยาลัยชั้นนำของโลก รับโปรแกรม PG สำหรับผู้บริหาร โปรแกรมประกาศนียบัตรขั้นสูง หรือโปรแกรมปริญญาโท เพื่อติดตามอาชีพของคุณอย่างรวดเร็ว

แอพพลิเคชั่นของ Priority Queue คืออะไร?

คิวลำดับความสำคัญคือคิวพิเศษที่องค์ประกอบจะถูกแทรกตามลำดับความสำคัญ คุณลักษณะนี้มีประโยชน์ในการใช้งานโครงสร้างข้อมูลอื่นๆ ต่อไปนี้คือแอปพลิเคชันยอดนิยมบางส่วนของคิวลำดับความสำคัญ:
 1. อัลกอริธึมเส้นทางที่สั้นที่สุดของ Dijkstra: คิวลำดับความสำคัญสามารถใช้ในอัลกอริธึมเส้นทางที่สั้นที่สุดของ Dijkstra เมื่อกราฟถูกจัดเก็บในรูปแบบของรายการที่อยู่ติดกัน
 2. อัลกอริธึมของ Prim : อัลกอริธึมของ Prim ใช้ลำดับความสำคัญของคิวกับค่าหรือคีย์ของโหนด และดึงค่าต่ำสุดเหล่านี้ออกในทุกขั้นตอน
 การบีบอัดข้อมูล : รหัส Huffman ใช้ลำดับความสำคัญในการบีบอัดข้อมูล
 ระบบปฏิบัติการ: คิวลำดับความสำคัญมีประโยชน์อย่างมากสำหรับระบบปฏิบัติการในกระบวนการต่างๆ เช่น การทำโหลดบาลานซ์และการจัดการการหยุดชะงัก

แนวทางใดที่ใช้ในการนำลำดับความสำคัญไปใช้โดยใช้อาร์เรย์

วิธีการที่ใช้ในการปรับใช้คิวลำดับความสำคัญโดยใช้อาร์เรย์นั้นง่าย โครงสร้างถูกสร้างขึ้นเพื่อเก็บค่าและลำดับความสำคัญขององค์ประกอบ จากนั้นอาร์เรย์ของโครงสร้างนั้นจะถูกสร้างขึ้นเพื่อจัดเก็บองค์ประกอบ การดำเนินการต่อไปนี้เกี่ยวข้องกับการใช้งานนี้:
 1. enqueue() - ฟังก์ชั่นนี้แทรกองค์ประกอบที่ส่วนท้ายของคิว
 2. peek() - ฟังก์ชั่นนี้จะสำรวจอาร์เรย์เพื่อส่งคืนองค์ประกอบที่มีลำดับความสำคัญสูงสุด หากพบองค์ประกอบสองรายการที่มีลำดับความสำคัญเท่ากัน ก็จะส่งกลับองค์ประกอบที่มีมูลค่าสูงสุดในบรรดาองค์ประกอบเหล่านั้น
 3. dequeue() - ฟังก์ชั่นนี้จะเปลี่ยนองค์ประกอบทั้งหมด 1 ตำแหน่งทางด้านซ้ายขององค์ประกอบที่ส่งคืนโดยฟังก์ชัน peek() และลดขนาด

ฮีปสูงสุดและฮีปขั้นต่ำแตกต่างกันอย่างไร

ต่อไปนี้แสดงให้เห็นถึงความแตกต่างระหว่างฮีปสูงสุดและฮีปขั้นต่ำ
 Min Heap - ใน min-heap คีย์ของรูทโหนดต้องน้อยกว่าหรือเท่ากับคีย์ของโหนดชายน์ มันใช้ลำดับความสำคัญจากน้อยไปมาก โหนดที่มีคีย์ที่เล็กที่สุดคือลำดับความสำคัญ องค์ประกอบที่เล็กที่สุดจะปรากฏก่อนองค์ประกอบอื่น
 Max Heap - ในฮีปสูงสุด คีย์ของรูทโหนดต้องมากกว่าหรือเท่ากับคีย์ของโหนดย่อย ใช้ลำดับความสำคัญจากมากไปหาน้อย โหนดที่มีคีย์ที่ใหญ่ที่สุดคือลำดับความสำคัญ องค์ประกอบที่ใหญ่ที่สุดจะปรากฏก่อนองค์ประกอบอื่น