คิวถัง
ชุดถังเก็บข้อมูลที่เหมาะสมสำหรับลำดับความสำคัญตั้งแต่ 1 ถึง 6 โดยองค์ประกอบที่มีลำดับความสำคัญต่ำที่สุดจะอยู่ในถังเก็บข้อมูลที่ไม่ว่างเปล่าทางซ้ายสุด
พิมพ์	คิวลำดับความสำคัญ
ประดิษฐ์	1969
คิดค้นโดย	โรเบิร์ต ไดอัล
ความซับซ้อนของเวลาในรูปแบบสัญกรณ์บิ๊กโอ การดำเนินการ เฉลี่ย กรณีที่เลวร้ายที่สุด แทรก O (1) O (1) หาค่าต่ำสุด O (#ลำดับความสำคัญ) O (#ลำดับความสำคัญ) ลบขั้นต่ำ O (#ลำดับความสำคัญ) O (#ลำดับความสำคัญ) ปุ่มลด O (1) O (1) ความซับซ้อนของพื้นที่

คิวแบบถัง ( Bucket queue ) เป็นโครงสร้างข้อมูลที่ใช้ ประเภทข้อมูล นามธรรมคิวลำดับความสำคัญ (Priority queue abstract data type ) โดยจะรักษากลุ่มขององค์ประกอบที่มีลำดับความสำคัญเป็นตัวเลขแบบไดนามิก และอนุญาตให้เข้าถึงองค์ประกอบที่มีลำดับความสำคัญต่ำสุด (หรือสูงสุด) ได้อย่างรวดเร็ว ในคิวแบบถัง ลำดับความสำคัญจะต้องเป็นจำนวนเต็มและเหมาะอย่างยิ่งสำหรับแอปพลิเคชันที่ลำดับความสำคัญมีช่วงแคบ^{[ 1 ]}คิวแบบถังมีรูปแบบเป็นอาร์เรย์ของถัง: โครงสร้างข้อมูลแบบอาร์เรย์ที่จัดทำดัชนีโดยลำดับความสำคัญ ซึ่งเซลล์ต่างๆ จะประกอบด้วยกลุ่มของรายการที่มีลำดับความสำคัญเท่ากัน ด้วยโครงสร้างข้อมูลนี้ การแทรกองค์ประกอบและการเปลี่ยนแปลงลำดับความสำคัญจะใช้เวลาคงที่การค้นหาและลบองค์ประกอบที่มีลำดับความสำคัญต่ำสุดจะใช้เวลาตามสัดส่วนของจำนวนถัง หรือโดยการรักษาตัวชี้ไปยังถังที่พบล่าสุด จะใช้เวลาตามสัดส่วนของความแตกต่างของลำดับความสำคัญระหว่างการดำเนินการที่ต่อเนื่องกัน

คิวแบบถัง (Bucket queue) เป็นคิวลำดับความสำคัญที่เทียบเคียงได้กับอัลกอริทึมการเรียงลำดับแบบรังนกพิราบ (Pigeonhole sort หรือเรียกอีกอย่างว่า bucket sort) ซึ่งเป็นอัลกอริทึมการเรียงลำดับที่วางองค์ประกอบลงในถังที่จัดทำดัชนีตามลำดับความสำคัญ จากนั้นจึงรวมถังเข้าด้วยกัน การใช้คิวแบบถังเป็นคิวลำดับความสำคัญในการเรียงลำดับ แบบเลือก (Selection sort ) จะให้รูปแบบหนึ่งของอัลกอริทึมการเรียงลำดับแบบรังนกพิราบ^{[ 2 ]}คิวแบบถังยังเรียกว่าคิวลำดับความสำคัญแบบถัง^{[ 3 ]}หรือคิวลำดับความสำคัญที่มีความสูงจำกัด^{[ 1 ]}เมื่อใช้สำหรับการประมาณค่าเชิงปริมาณของ ลำดับความสำคัญ ของจำนวนจริงพวกมันยังเรียกว่าคิวลำดับความสำคัญที่ไม่เป็นระเบียบ^{[ 4 ]}หรือคิวลำดับความสำคัญเทียม^{[ 5 ]}พวกมันมีความเกี่ยวข้องอย่างใกล้ชิดกับคิวปฏิทิน (Calendar queue ) ซึ่งเป็นโครงสร้างที่ใช้อาร์เรย์ของถังที่คล้ายกันสำหรับการจัดลำดับความสำคัญที่แน่นอนด้วยจำนวนจริง

การประยุกต์ใช้คิวแบบถัง ได้แก่ การคำนวณความเสื่อมของกราฟอัลกอริทึมที่รวดเร็วสำหรับเส้นทางที่สั้นที่สุดและเส้นทางที่กว้างที่สุดสำหรับกราฟที่มีน้ำหนักเป็นจำนวนเต็มขนาดเล็กหรือเรียงลำดับแล้ว และอัลกอริทึมการประมาณค่า แบบโลภ สำหรับปัญหาการครอบคลุมเซตเวอร์ชันควอนไทซ์ของโครงสร้างนี้ยังถูกนำไปใช้กับการจัดตารางเวลา^{[ 2 ]}และลูกบาศก์เดินในกราฟิกคอมพิวเตอร์ [ ^{4 ] การ}ใช้คิวแบบถังครั้งแรก^{[ 6 ]}อยู่ในอัลกอริทึมเส้นทางที่สั้นที่สุดโดยDial (1969 ) ^{[ 7 ]}

คิวแบบบัคเก็ตสามารถจัดการองค์ประกอบที่มีลำดับความสำคัญเป็นจำนวนเต็มในช่วงตั้งแต่ 0 หรือ 1 ไปจนถึงขอบเขตที่ทราบCและการดำเนินการที่แทรกองค์ประกอบ เปลี่ยนลำดับความสำคัญขององค์ประกอบ หรือแยก (ค้นหาและลบ) องค์ประกอบที่มีลำดับความสำคัญต่ำสุด (หรือสูงสุด) ประกอบด้วยอาร์เรย์Aของโครงสร้างข้อมูลคอนเทนเนอร์ในแหล่งข้อมูลส่วนใหญ่ คอนเทนเนอร์เหล่านี้เป็นรายการเชื่อมโยงแบบสองทิศทางแต่อาจเป็นอาร์เรย์ไดนามิก^{[ 3 ]}หรือเซตไดนามิก ก็ได้ คอนเทนเนอร์ในเซลล์อาร์เรย์ที่p ของ A [ p ] จะเก็บคอล เลกชันขององค์ประกอบที่มีลำดับความสำคัญเป็นp

คิวแบบบัคเก็ตสามารถจัดการการดำเนินการต่อไปนี้ได้:

• ในการแทรกองค์ประกอบxที่มีลำดับความสำคัญpให้เพิ่มxลงในคอนเทนเนอร์ที่A [ p ]
• หากต้องการเปลี่ยนลำดับความสำคัญขององค์ประกอบ ให้ลบองค์ประกอบนั้นออกจากคอนเทนเนอร์สำหรับลำดับความสำคัญเดิม แล้วใส่กลับเข้าไปในคอนเทนเนอร์สำหรับลำดับความสำคัญใหม่
• ในการดึงองค์ประกอบที่มีลำดับความสำคัญต่ำสุดหรือสูงสุด ให้ทำการค้นหาตามลำดับในอาร์เรย์เพื่อหาภาชนะที่ไม่ว่างเปล่าแรกหรือสุดท้ายตามลำดับ เลือกองค์ประกอบใดๆ จากภาชนะนั้น และลบออกจากภาชนะ

ด้วย วิธีนี้ การแทรกและการเปลี่ยนแปลงลำดับความสำคัญจะใช้เวลาคงที่ และการดึงองค์ประกอบที่มีลำดับความสำคัญต่ำสุดหรือสูงสุดจะใช้เวลาO ( C ) ^{[ 1 ] [ 6 ] [ 8 ]}

เพื่อเป็นการปรับปรุงประสิทธิภาพ โครงสร้างข้อมูลสามารถเริ่มต้นการค้นหาแบบลำดับสำหรับบัคเก็ตที่ไม่ว่างเปล่าที่บัคเก็ตที่ไม่ว่างเปล่าที่พบเมื่อเร็ว ๆ นี้ แทนที่จะเริ่มต้นที่จุดเริ่มต้นของอาร์เรย์ ซึ่งสามารถทำได้สองวิธี คือ แบบเลซี่ (เลื่อนการค้นหาแบบลำดับเหล่านี้ออกไปจนกว่าจะจำเป็น) หรือแบบเอียร์ (ทำการค้นหาล่วงหน้า) การเลือกเวลาที่จะทำการค้นหาจะส่งผลต่อการดำเนินการใดของโครงสร้างข้อมูลที่ช้าลงเนื่องจากการค้นหาเหล่านี้ เวอร์ชันดั้งเดิมของโครงสร้าง Dial ใช้การค้นหาแบบเลซี่ ซึ่งสามารถทำได้โดยการรักษาดัชนีLที่เป็นขอบล่างของลำดับความสำคัญต่ำสุดขององค์ประกอบใด ๆ ที่อยู่ในคิวในปัจจุบัน เมื่อแทรกองค์ประกอบใหม่Lควรได้รับการอัปเดตเป็นค่าต่ำสุดของค่าเดิมและลำดับความสำคัญขององค์ประกอบใหม่ เมื่อค้นหาองค์ประกอบที่มีลำดับความสำคัญต่ำสุด การค้นหาสามารถเริ่มต้นที่Lแทนที่จะเป็นศูนย์ และหลังจากการค้นหาLควรมีค่าเท่ากับลำดับความสำคัญที่พบในการค้นหา^{[ 7 ] [ 9 ]}หรืออีกทางหนึ่ง เวอร์ชันแบบเอียร์ของการปรับปรุงประสิทธิภาพนี้จะ อัปเดต L อยู่ เสมอเพื่อให้ชี้ไปยังบัคเก็ตที่ไม่ว่างเปล่าแรกเสมอ เมื่อแทรกองค์ประกอบใหม่ที่มีลำดับความสำคัญน้อยกว่าLโครงสร้างข้อมูลจะตั้งค่าLเป็นลำดับความสำคัญใหม่ และเมื่อลบองค์ประกอบสุดท้ายออกจากบัคเก็ตที่มีลำดับความสำคัญLระบบจะทำการค้นหาตามลำดับผ่านดัชนีที่ใหญ่กว่าจนกว่าจะพบบัคเก็ตที่ไม่ว่างเปล่าและตั้งค่าLเป็นลำดับความสำคัญของบัคเก็ตที่ได้^{[ 1 ]}

ในทั้งสองรูปแบบนี้ การค้นหาแบบลำดับแต่ละครั้งจะใช้เวลาแปรผันตามความแตกต่างระหว่างค่าL เก่าและค่า L ใหม่ ซึ่งอาจเร็วกว่า ขอบเขตเวลา O ( C )สำหรับการค้นหาในโครงสร้างข้อมูลที่ยังไม่ได้ปรับให้เหมาะสมอย่างมาก ในการใช้งานคิวลำดับความสำคัญหลายๆ อย่าง เช่นอัลกอริทึมของ Dijkstraลำดับความสำคัญต่ำสุดจะก่อให้เกิดลำดับโมโนโทนิกทำให้สามารถ ใช้ คิวลำดับความสำคัญแบบโมโนโทนิกได้ในการใช้งานเหล่านี้ สำหรับทั้งรูปแบบ lazy และ eager ของโครงสร้างที่ปรับให้เหมาะสมแล้ว การค้นหาแบบลำดับสำหรับบัคเก็ตที่ไม่ว่างเปล่าจะครอบคลุมช่วงของบัคเก็ตที่ไม่ซ้ำกัน เนื่องจากแต่ละบัคเก็ตอยู่ในช่วงเหล่านี้อย่างมากที่สุดหนึ่งช่วง จำนวนขั้นตอนจึงรวมกันได้มากที่สุดCดังนั้น ในการใช้งานเหล่านี้ เวลาทั้งหมดสำหรับลำดับของ การดำเนินการ nครั้งคือO ( n + C )แทนที่จะเป็น ขอบเขตเวลา O ( nC ) ที่ช้ากว่า ซึ่งจะเกิดขึ้นหากไม่มีการปรับให้เหมาะสมนี้^{[ 9 ]}การปรับปรุงที่สอดคล้องกันสามารถนำไปใช้ในแอปพลิเคชันที่ใช้คิวแบบถังเพื่อค้นหาองค์ประกอบที่มีลำดับความสำคัญสูงสุด แต่ในกรณีนี้ควรรักษาดัชนีที่จำกัดลำดับความสำคัญสูงสุดไว้ และการค้นหาถังที่ไม่ว่างตามลำดับควรดำเนินการลงมาจากขอบเขตบนนี้^{[ 10 ]}

การปรับปรุงประสิทธิภาพอีกอย่างหนึ่ง (ซึ่งDial ได้ให้ไว้แล้วในปี 1969 ) สามารถใช้เพื่อประหยัดพื้นที่เมื่อลำดับความสำคัญเป็นแบบโมโนโทนิก และตลอดการทำงานของอัลกอริทึม ลำดับความสำคัญจะอยู่ในช่วง ค่า r เสมอ แทนที่จะขยายไปทั่วทั้งช่วงตั้งแต่ 0 ถึงCในกรณีนี้ เราสามารถจัดทำดัชนีอาร์เรย์โดยใช้ลำดับความสำคัญแบบโมดูลัสr แทนที่จะใช้ค่าจริง การค้นหาองค์ประกอบที่มีลำดับความสำคัญต่ำสุดควรเริ่มต้นที่ค่าต่ำสุดก่อนหน้าเสมอ เพื่อหลีกเลี่ยงลำดับความสำคัญที่สูงกว่าค่าต่ำสุดแต่มีโมดูลัสต่ำกว่า โดยเฉพาะอย่างยิ่ง แนวคิดนี้สามารถนำไปใช้ในอัลกอริทึมของ Dijkstra บนกราฟที่มีความ ^ยาวขอบเป็นจำนวนเต็มในช่วงตั้งแต่ 1 ถึงr ^{[ 8} ]

เนื่องจากการสร้างคิวบัคเก็ตใหม่เกี่ยวข้องกับการเริ่มต้นอาร์เรย์ของบัคเก็ตว่าง ขั้นตอนการเริ่มต้นนี้จึงใช้เวลาตามสัดส่วนของจำนวนลำดับความสำคัญ คิวบัคเก็ตแบบหนึ่งที่Donald B. Johnson อธิบายไว้ ในปี 1981 จะเก็บเฉพาะบัคเก็ตที่ไม่ว่างไว้ในรายการเชื่อมโยง โดยเรียงลำดับตามลำดับความสำคัญ และใช้ต้นไม้ค้นหาเสริมเพื่อค้นหาตำแหน่งในรายการเชื่อมโยงนี้สำหรับบัคเก็ตใหม่ได้อย่างรวดเร็ว การเริ่มต้นโครงสร้างแบบแปรผันนี้ใช้เวลาO (log log C ) ใช้ เวลาคงที่ในการค้นหาองค์ประกอบที่มีลำดับความสำคัญต่ำสุดหรือสูงสุด และใช้เวลาO (log log D )ในการแทรกหรือลบองค์ประกอบ โดยที่Dคือความแตกต่างระหว่างลำดับความสำคัญที่เล็กกว่าและใหญ่กว่าที่ใกล้ที่สุดกับลำดับความสำคัญขององค์ประกอบที่แทรกหรือลบ^{[ 11 ]}

ตัวอย่างเช่น พิจารณาคิวแบบถังที่มีลำดับความสำคัญสี่ระดับ คือ 0, 1, 2 และ 3 คิวนี้ประกอบด้วยอาร์เรย์ที่มีเซลล์สี่เซลล์แต่ละเซลล์บรรจุชุดขององค์ประกอบ ซึ่งเริ่มต้นว่างเปล่า สำหรับตัวอย่างนี้สามารถเขียนได้เป็นลำดับวงเล็บของชุดสี่ชุด: พิจารณาลำดับของการดำเนินการที่เราแทรกองค์ประกอบสองตัวคือและที่มีลำดับความสำคัญเท่ากันคือ 1 แทรกองค์ประกอบที่สามที่มีลำดับความสำคัญ 3 เปลี่ยนลำดับความสำคัญของเป็น 3 จากนั้นทำการดึงองค์ประกอบที่มีลำดับความสำคัญต่ำสุดสองครั้ง ${\displaystyle A}$${\displaystyle A}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x}$

• หลังจากแทรกด้วยลำดับความสำคัญ 1 แล้ว.${\displaystyle x}$${\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}$
• หลังจากแทรกด้วยลำดับความสำคัญ 1 แล้ว.${\displaystyle y}$${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}$
• หลังจากแทรก z ด้วยลำดับความสำคัญ 3 แล้ว.${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}$
• การเปลี่ยนลำดับความสำคัญของ x จาก 1 เป็น 3 นั้นเกี่ยวข้องกับการลบออกจากและเพิ่มเข้าไปใน จากนั้นจึงดำเนินการต่อไป${\displaystyle A[1]}$${\displaystyle A[3]}$${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$
• ในเวอร์ชันพื้นฐานของคิวแบบบัคเก็ต การดึงองค์ประกอบที่มีลำดับความสำคัญต่ำสุด จะค้นหาจากจุดเริ่มต้นเพื่อหาองค์ประกอบที่ไม่ว่างเปล่าตัวแรก: นั้นว่างเปล่า แต่เป็นเซตที่ไม่ว่างเปล่า มันจะเลือกองค์ประกอบใดๆ จากเซตนี้ (องค์ประกอบเดียว คือ) เป็นองค์ประกอบที่มีลำดับความสำคัญต่ำสุด การลบ ออกจากโครงสร้างจะเหลือ${\displaystyle A}$${\displaystyle A[0]}$${\displaystyle A[1]=\{y\}}$${\displaystyle y}$${\displaystyle y}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}$
• การดำเนินการดึงข้อมูลครั้งที่สอง ในเวอร์ชันพื้นฐานของคิวแบบบัคเก็ต จะค้นหาอีกครั้งจากจุดเริ่มต้นของอาร์เรย์: , , , ที่ไม่ว่างเปล่า ในเวอร์ชันที่ปรับปรุงแล้วของคิวแบบบัคเก็ต การค้นหานี้จะเริ่มต้นที่ตำแหน่งสุดท้ายที่พบว่าไม่ว่างเปล่าแทนในทั้งสองกรณีพบว่าเป็นเซตที่ไม่ว่างเปล่าชุดแรก เลือกองค์ประกอบหนึ่งในนั้นโดยพลการเป็นองค์ประกอบที่มีลำดับความสำคัญต่ำสุด ตัวอย่างเช่นอาจเลือก องค์ประกอบนี้จะถูกลบออก เหลือไว้เพียง${\displaystyle A[0]=\emptyset }$${\displaystyle A[1]=\emptyset }$${\displaystyle A[2]=\emptyset }$${\displaystyle A[3]={}}$${\displaystyle A[1]}$${\displaystyle A[3]=\{x,z\}}$${\displaystyle z}$${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}$

สามารถใช้คิวแบบถังเพื่อดูแลจุดยอดของกราฟแบบไม่มีทิศทางโดยจัดลำดับความสำคัญตามดีกรีและค้นหาและลบจุดยอดที่มีดีกรีต่ำสุดซ้ำๆ^{[ 1 ]}อัลกอริทึมแบบโลภนี้สามารถใช้ในการคำนวณความเสื่อมของกราฟที่กำหนด ซึ่งเท่ากับดีกรีสูงสุดของจุดยอดใดๆ ในขณะที่ลบออก อัลกอริทึมนี้ใช้เวลาเชิงเส้นไม่ว่าจะมีหรือไม่มีการเพิ่มประสิทธิภาพที่รักษาขอบเขตล่างของลำดับความสำคัญขั้นต่ำ เนื่องจากแต่ละจุดยอดจะถูกค้นพบในเวลาที่แปรผันตามดีกรี และผลรวมของดีกรีของจุดยอดทั้งหมดเป็นเชิงเส้นตามจำนวนขอบของกราฟ^{[ 12 ]}

ในอัลกอริทึมของ Dijkstra สำหรับเส้นทางที่สั้นที่สุดในกราฟแบบมีทิศทางที่มีน้ำหนักขอบเป็นจำนวนเต็มบวก ลำดับความสำคัญจะเป็นแบบโมโนโทน^{[ 13 ]}และสามารถใช้คิวแบบบัคเก็ตโมโนโทนเพื่อให้ได้ขอบเขตเวลาO ( m + dc )โดยที่mคือจำนวนขอบdคือเส้นผ่านศูนย์กลางของเครือข่าย และcคือต้นทุนลิงก์สูงสุด (จำนวนเต็ม) ^{[ 9 ] [ 14 ]}รูปแบบนี้ของอัลกอริทึมของ Dijkstra ยังเป็นที่รู้จักในชื่อ อัลกอริทึม ของDial ^{[ 9 ]}ตามชื่อของ Robert B. Dial ผู้ตีพิมพ์ในปี 1969 ^{[ 7 ]}แนวคิดเดียวกันนี้ยังใช้ได้ผลเช่นกัน โดยใช้คิวแบบบัคเก็ตควอนไทซ์ สำหรับกราฟที่มีน้ำหนักขอบจริงบวก เมื่ออัตราส่วนของน้ำหนักสูงสุดต่อน้ำหนักต่ำสุดมีค่าไม่เกินc ^{[ 15 ]}ในเวอร์ชันควอนไทซ์ของอัลกอริทึมนี้ จุดยอดจะถูกประมวลผลนอกลำดับ เมื่อเปรียบเทียบกับผลลัพธ์ที่มีคิวลำดับความสำคัญแบบไม่ควอนไทซ์ แต่เส้นทางที่สั้นที่สุดที่ถูกต้องก็ยังคงถูกค้นพบ^{[ 5 ]}ในอัลกอริทึมเหล่านี้ ลำดับความสำคัญจะครอบคลุมช่วงความกว้างc + 1 เท่านั้น ดังนั้นการเพิ่มประสิทธิภาพแบบโมดูลาร์จึงสามารถใช้เพื่อลดพื้นที่เป็นO ( n + c )ได้^{[ 8 ] [ 14 ]}

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

ปัญหาการครอบคลุมเซตมีอินพุตเป็นกลุ่มของเซตเอาต์พุตควรเป็นกลุ่มย่อยของเซตเหล่านี้ โดยมีการรวมกันเหมือนกับกลุ่มดั้งเดิม และรวมเซตให้น้อยที่สุดเท่าที่จะเป็นไปได้ ปัญหานี้เป็นปัญหาNP-hardแต่มีอัลกอริทึมการประมาณแบบโลภที่ให้ค่าประมาณแบบลอการิทึม ซึ่งโดยพื้นฐานแล้วเป็นค่าที่ดีที่สุดเท่าที่จะเป็นไปได้ เว้นแต่ว่าP = NP [ ^{17 ] อั}ลกอริทึมการประมาณนี้เลือกกลุ่มย่อยโดยการเลือกเซตที่ครอบคลุมจำนวนองค์ประกอบที่ยังไม่ถูกครอบคลุมมากที่สุดเท่าที่จะเป็นไปได้ซ้ำๆ^{[ 18 ]}แบบฝึกหัดมาตรฐานในการออกแบบอัลกอริทึมขอให้มีการนำอัลกอริทึมนี้ไปใช้โดยใช้เวลาเชิงเส้นตามขนาดของอินพุต ซึ่งก็คือผลรวมของขนาดของเซตอินพุตทั้งหมด^{[ 19 ]}

อาจแก้ปัญหานี้ได้โดยใช้คิวแบบถังของเซตในตระกูลอินพุต โดยจัดลำดับความสำคัญตามจำนวนองค์ประกอบที่เหลือที่ครอบคลุม ในแต่ละครั้งที่อัลกอริทึมแบบโลภเลือกเซตเป็นส่วนหนึ่งของเอาต์พุต องค์ประกอบของเซตที่ครอบคลุมใหม่ควรถูกลบออกจากลำดับความสำคัญของเซตอื่นๆ ที่ครอบคลุมองค์ประกอบเหล่านั้น ในระหว่างการทำงานของอัลกอริทึม จำนวนการเปลี่ยนแปลงลำดับความสำคัญเหล่านี้จะเท่ากับผลรวมของขนาดของเซตอินพุต ลำดับความสำคัญเป็นจำนวนเต็มที่ลดลงอย่างต่อเนื่อง โดยมีขอบเขตบนตามจำนวนองค์ประกอบที่จะต้องครอบคลุม การเลือกแต่ละครั้งของอัลกอริทึมแบบโลภเกี่ยวข้องกับการค้นหาเซตที่มีลำดับความสำคัญสูงสุด ซึ่งสามารถทำได้โดยการสแกนลงไปตามถังของคิวแบบถัง โดยเริ่มจากค่าสูงสุดก่อนหน้าล่าสุด เวลาทั้งหมดเป็นเชิงเส้นตามขนาดของอินพุต^{[ 10 ]}

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

โครงสร้างข้อมูลคิวแบบแบ่งกลุ่มที่มีการควอนไทซ์ (quantized bucket queue) รูปแบบหนึ่งที่เรียกว่า คิวปฏิทิน ( calendar queue ) ได้ถูกนำมาประยุกต์ใช้ในการจัดตาราง เวลาสำหรับการจำลองเหตุการณ์แบบไม่ต่อเนื่อง (discrete-event simulations)โดยที่องค์ประกอบในคิวคือเหตุการณ์ในอนาคตที่จัดลำดับความสำคัญตามเวลาภายในของการจำลองที่เหตุการณ์เหล่านั้นควรเกิดขึ้น ในแอปพลิเคชันนี้ ลำดับของเหตุการณ์มีความสำคัญอย่างยิ่ง ดังนั้นจึงไม่สามารถประมาณลำดับความสำคัญได้ ด้วยเหตุนี้ คิวปฏิทินจึงทำการค้นหาองค์ประกอบที่มีลำดับความสำคัญต่ำสุดในลักษณะที่แตกต่างจากคิวแบบแบ่งกลุ่ม: ในคิวแบบแบ่งกลุ่ม องค์ประกอบใดๆ ก็ได้ในถังแรกที่ไม่ว่างเปล่าอาจถูกส่งคืน แต่คิวปฏิทินจะค้นหาองค์ประกอบทั้งหมดในถังนั้นเพื่อพิจารณาว่าองค์ประกอบใดมีลำดับความสำคัญที่ไม่ถูกควอนไทซ์น้อยที่สุด เพื่อให้การค้นหาเหล่านี้รวดเร็ว รูปแบบนี้พยายามรักษาสัดส่วนของจำนวนถังให้เท่ากับจำนวนองค์ประกอบ โดยการปรับขนาดของการควอนไทซ์และสร้างโครงสร้างข้อมูลใหม่เมื่อเกิดความไม่สมดุล คิวปฏิทินอาจช้ากว่าคิวถังในกรณีที่เลวร้ายที่สุด (เมื่อองค์ประกอบจำนวนมากตกอยู่ในถังที่เล็กที่สุดเดียวกัน) แต่จะเร็วเมื่อองค์ประกอบกระจายอย่างสม่ำเสมอในถังต่างๆ ทำให้ขนาดถังโดยเฉลี่ยคงที่^{[ 20 ] [ 21 ]}

ในคณิตศาสตร์ประยุกต์และวิธีการเชิงตัวเลขสำหรับการแก้สมการเชิงอนุพันธ์คิวลำดับความสำคัญที่ไม่เป็นระเบียบถูกนำมาใช้เพื่อจัดลำดับความสำคัญของขั้นตอนของวิธีการเดินเร็วสำหรับการแก้ปัญหาค่าขอบเขตของสมการ Eikonalซึ่งใช้ในการจำลองการแพร่กระจายของคลื่นวิธีนี้ค้นหาเวลาที่ขอบเขตที่เคลื่อนที่ตัดผ่านชุดของจุดที่ไม่ต่อเนื่อง (เช่น จุดของตารางจำนวนเต็ม) โดยใช้วิธีการจัดลำดับความสำคัญที่คล้ายกับเวอร์ชันต่อเนื่องของ อัลกอริทึมของ Dijkstraและเวลาในการทำงานจะถูกครอบงำโดยคิวลำดับความสำคัญของจุดเหล่านี้ สามารถเร่งความเร็วให้เป็นเวลาเชิงเส้นได้โดยการปัดเศษลำดับความสำคัญที่ใช้ในอัลกอริทึมนี้ให้เป็นจำนวนเต็ม และใช้คิวแบบถังสำหรับจำนวนเต็มเหล่านี้ เช่นเดียวกับในอัลกอริทึมของ Dijkstra และ Dial ลำดับความสำคัญเป็นแบบโมโนโทน ดังนั้นการเดินเร็วจึงสามารถใช้การเพิ่มประสิทธิภาพแบบโมโนโทนของคิวแบบถังและการวิเคราะห์ได้ อย่างไรก็ตาม การแบ่งส่วนย่อยทำให้เกิดข้อผิดพลาดบางอย่างในการคำนวณที่ได้^{[ 4 ]}

• ซอฟต์ฮีป (Soft heap)คือวิธีการเร่งความเร็วคิวลำดับความสำคัญแบบใหม่ โดยใช้ลำดับความสำคัญโดยประมาณ