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

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

ทั้งโครงสร้างข้อมูลและชื่อของมันได้รับการคิดค้นโดยJohn IaconoและStefan Langerman ^{[ 1 ]}

คิวแพป (queap) เป็นคิวลำดับความสำคัญที่แทรกองค์ประกอบใน เวลาเฉลี่ย O (1) และลบองค์ประกอบขั้นต่ำในเวลาO (log( k  + 2)) หากมี รายการ kรายการที่อยู่ในฮีปเป็นเวลานานกว่าองค์ประกอบที่จะถูกดึงออกมา คิวแพปมีคุณสมบัติที่เรียกว่าคุณสมบัติแบบคิว (queueish property): เวลาในการค้นหาองค์ประกอบxคือ O(lg q ( x )) โดยที่q ( x ) เท่ากับn  − 1 −  w ( x ) และw ( x ) คือจำนวนรายการที่แตกต่างกันที่ถูกเข้าถึงโดยการดำเนินการต่างๆ เช่น การค้นหา การแทรก หรือการลบq ( x ) ถูกกำหนดให้เป็นจำนวนองค์ประกอบที่ไม่ถูกเข้าถึงตั้งแต่ การเข้าถึง xครั้งล่าสุด อันที่จริง คุณสมบัติแบบคิวเป็นส่วนเติมเต็มของคุณสมบัติชุดการทำงานของสไปลทรี (splay tree working set property): เวลาในการค้นหาองค์ประกอบxคือO (lg w ( x ))

คิวสามารถแสดงได้ด้วยโครงสร้างข้อมูลสองแบบ ได้แก่ รายการเชื่อมโยงสองทิศทางและต้นไม้ 2–4 ที่ดัดแปลงแล้ว รายการเชื่อมโยงสองทิศทางLใช้สำหรับการดำเนินการแทรกและค้นหาค่าต่ำสุดหลายรายการ คิวจะเก็บตัวชี้ไปยังองค์ประกอบที่เล็กที่สุดที่เก็บไว้ในรายการ ในการเพิ่มองค์ประกอบxลงในรายการlองค์ประกอบxจะถูกเพิ่มเข้าไปที่ท้ายรายการ และตัวแปรบิตในองค์ประกอบxจะถูกตั้งค่าเป็นหนึ่ง การดำเนินการนี้ทำขึ้นเพื่อตรวจสอบว่าองค์ประกอบนั้นอยู่ในรายการหรืออยู่ในต้นไม้ 2–4 หรือไม่

จะใช้โครงสร้างต้นไม้ 2–4 เมื่อมีการดำเนินการลบ หากรายการxอยู่ในต้นไม้T อยู่แล้ว รายการนั้นจะถูกลบออกโดยใช้การดำเนินการลบของต้นไม้ 2–4 มิเช่นนั้น รายการxจะอยู่ในรายการL (โดยการตรวจสอบว่าตัวแปรบิตถูกตั้งค่าหรือไม่) จากนั้นองค์ประกอบทั้งหมดที่เก็บไว้ในรายการLจะถูกเพิ่มเข้าไปในต้นไม้ 2–4 โดยตั้งค่าตัวแปรบิตของแต่ละองค์ประกอบเป็นศูนย์ จากนั้นx จะถูกลบออกจากT

คิวแอพใช้เฉพาะคุณสมบัติของโครงสร้างต้นไม้ 2–4 เท่านั้น ไม่ได้ใช้โครงสร้างต้นไม้ค้นหา โครงสร้างต้นไม้ 2–4 ที่ดัดแปลงแล้วมีดังนี้ สมมติว่าลิสต์Lมีเซตขององค์ประกอบดังต่อไปนี้: เมื่อมีการเรียกใช้การดำเนินการลบ เซตขององค์ประกอบที่เก็บไว้ในLจะถูกเพิ่มเข้าไปในใบของต้นไม้ 2–4 ตามลำดับนั้น โดยมีใบดัมมี่ที่มีคีย์อนันต์นำหน้า แต่ละโหนดภายในของTมีตัวชี้ซึ่งชี้ไปยังรายการที่เล็กที่สุดในต้นไม้ย่อยvแต่ละโหนดภายในบนเส้นทางPจากรากไปยังมีตัวชี้ซึ่งชี้ไปยังคีย์ที่เล็กที่สุดในตัว ชี้ของแต่ละโหนดภายในบนเส้นทางPจะถูกละเลย คิวแอพมีตัวชี้ไปยังซึ่งชี้ไปยังองค์ประกอบที่เล็กที่สุดในT${\displaystyle x_{1},x_{2},x_{3},\dots ,x_{k}}$${\displaystyle h_{v}}$${\displaystyle x_{0}}$${\displaystyle c_{v}}$${\displaystyle T-T_{v}-\{r\}}$${\displaystyle h_{v}}$${\displaystyle c_{x_{0}}}$

การประยุกต์ใช้คิวประกอบด้วยชุดเหตุการณ์ที่มีลำดับความสำคัญสูงเฉพาะ และการดึงเหตุการณ์ที่มีลำดับความสำคัญสูงสุดออกมาเพื่อประมวลผล

ให้minLเป็นตัวชี้ที่ชี้ไปยังองค์ประกอบที่เล็กที่สุดในรายการเชื่อมโยงสองทิศทางL , เป็นองค์ประกอบที่เล็กที่สุดที่เก็บไว้ในต้นไม้ 2–4, T , kเป็นจำนวนองค์ประกอบที่เก็บไว้ในTและnเป็นจำนวนองค์ประกอบทั้งหมดที่เก็บไว้ในคิวQการดำเนินการมีดังต่อไปนี้: ${\displaystyle c_{x_{0}}}$

New(Q):สร้างคิวว่างใหม่ขึ้นมา

เริ่มต้นด้วยลิสต์เชื่อมโยงสองทางว่างเปล่าLและต้นไม้ 2–4 Tกำหนดค่าkและnเป็นศูนย์

Insert(Q, x):เพิ่ม องค์ประกอบ xลงในคิว Q

แทรกองค์ประกอบxลงในรายการLตั้งค่าบิตในองค์ประกอบxเป็นหนึ่งเพื่อแสดงว่าองค์ประกอบนั้นอยู่ในรายการLอัปเดต ตัวชี้ minLถ้าxเป็นองค์ประกอบที่เล็กที่สุดในรายการ เพิ่มค่าnขึ้น 1

Minimum(Q):ดึงพอยเตอร์ไปยังองค์ประกอบที่เล็กที่สุดจากคิว Q

ถ้าkey(minL) < key ( ) ให้คืนค่าminLมิฉะนั้นให้คืนค่า.${\displaystyle c_{x_{0}}}$${\displaystyle c_{x_{0}}}$

Delete(Q, x):ลบองค์ประกอบ x ออกจากคิว Q

ถ้าบิตขององค์ประกอบxถูกตั้งค่าเป็นหนึ่ง องค์ประกอบนั้นจะถูกเก็บไว้ในลิสต์Lเพิ่มองค์ประกอบทั้งหมดจากLไปยังTโดยตั้งค่าบิตของแต่ละองค์ประกอบเป็นศูนย์ แต่ละองค์ประกอบจะถูกเพิ่มเข้าไปในโหนดแม่ของโหนดลูกขวาสุดของTโดยใช้การดำเนินการแทรกของต้นไม้ 2–4 Lจะว่างเปล่า อัปเดตตัวชี้สำหรับโหนดv ทั้งหมด ที่มีโหนดลูกใหม่/ที่แก้ไขแล้ว และทำซ้ำกระบวนการกับโหนดแม่ถัดไปจนกว่าโหนดแม่จะเท่ากับโหนดราก เดินจากโหนดรากไปยังโหนด และอัปเดตค่าตั้งค่าkเท่ากับn${\displaystyle h_{v}}$${\displaystyle x_{0}}$${\displaystyle c_{v}}$

ถ้าบิตขององค์ประกอบxถูกตั้งค่าเป็นศูนย์ แสดงว่าxเป็นใบของTลบ x โดยใช้การดำเนินการลบต้นไม้แบบ 2–4 เริ่มจากโหนดxเดินในTไปยังโหนดอัปเดตตัว ชี้ n และk ลดค่า n และ k ลง 1${\displaystyle x_{0}}$${\displaystyle h_{v}}$${\displaystyle c_{v}}$

DeleteMin(Q):ลบและส่งคืนองค์ประกอบที่เล็กที่สุดจากคิว Q

เรียกใช้ การดำเนินการ Minimum(Q)การดำเนินการนี้จะส่งคืนค่าminเรียกใช้ การดำเนินการ Delete(Q, min)การดำเนินการนี้จะส่งคืนค่าmin

CleanUp(Q):ลบองค์ประกอบทั้งหมดในรายการ Lและต้นไม้ T

เริ่มต้นจากองค์ประกอบแรกในรายการLวนไปตามรายการและลบแต่ละโหนดออก

เริ่มต้นจากโหนดรากของต้นไม้Tท่องไปในต้นไม้โดยใช้ อัลกอริทึม การท่องแบบโพสต์ออร์เดอร์โดยลบแต่ละโหนดในต้นไม้

เวลาในการทำงานจะถูกวิเคราะห์โดยใช้การวิเคราะห์แบบถัวเฉลี่ยฟังก์ชันศักยภาพสำหรับคิว Q จะเป็นโดย ที่${\displaystyle \phi (Q)=c|L|}$${\displaystyle Q=(T,L)}$

Insert(Q, x):ต้นทุนของการดำเนินการคือ O(1)ขนาดของรายการ Lเพิ่มขึ้นหนึ่ง และศักยภาพเพิ่มขึ้นตามค่าคงที่ c บาง ค่า

ขั้นต่ำ(Q):การดำเนินการจะไม่เปลี่ยนแปลงโครงสร้างข้อมูล ดังนั้นต้นทุนเฉลี่ยจึงเท่ากับต้นทุนจริง O(1)

ลบ (Q, x):มีสองกรณี

ถ้าxอยู่ในต้นไม้Tต้นทุนเฉลี่ยจะไม่เปลี่ยนแปลง การดำเนินการลบเป็นO(1)ต้นทุนเฉลี่ยสำหรับต้นไม้ 2–4 เนื่องจากxถูกลบออกจากต้นไม้แล้วตัวชี้อาจต้องได้รับการอัปเดต อย่างมากที่สุดจะมีการอัปเดต ${\displaystyle h_{v}}$${\displaystyle c_{v}}$${\displaystyle O(lgq(x))}$

ถ้าxอยู่ในลิสต์Lแล้ว องค์ประกอบทั้งหมดจากLจะถูกแทรกเข้าไปในTการดำเนินการนี้มีค่าใช้จ่ายเท่ากับ ค่าคงที่ aบางค่าซึ่งเฉลี่ยแล้วบนต้นไม้ 2–4 หลังจากแทรกและอัปเดต ตัวชี้ และแล้ว เวลาที่ใช้ทั้งหมดจะถูกจำกัดด้วยการดำเนินการที่สองคือการลบx ออก จากTและเดินไปตามเส้นทางจาก x ไปยังโดยแก้ไข ค่า และเวลาที่ใช้จะมากที่สุด ถ้าค่าใช้จ่ายเฉลี่ยจะเป็นDelete (Q, x):คือผลรวมของค่าใช้จ่ายเฉลี่ยของMinimum(Q)และDelete(Q, x)ซึ่งคือ ${\displaystyle a|L|}$${\displaystyle h_{v}}$${\displaystyle c_{v}}$${\displaystyle 2a|L|}$${\displaystyle x_{0}}$${\displaystyle h_{v}}$${\displaystyle c_{v}}$${\displaystyle 2a|L|+O(lgq(x))}$${\displaystyle c>2a}$${\displaystyle O(lgq(x))}$${\displaystyle O(lgq(x))}$

ตัวอย่างการใช้งานคิว (queap) ขนาดเล็ก ใน ภาษา Java :

public class Queap { public int n , k ; public List < Element > l ; // Element เป็นชนิดข้อมูลทั่วไปpublic QueapTree t ; // ต้นไม้ 2-4 ที่ดัดแปลงเพื่อวัตถุประสงค์ของ Queap public Element minL ;private Queap () { n = 0 ; k = 0 ; l = new LinkedList <Element> ( ); t = new QueapTree () ; }public static Queap New () { return new Queap (); }public static void Insert ( Queup Q , Element x ) { if ( Q.n == 0 ) Q.minL = x ; Q.l.add ( x ) ; x.inList = true ; if ( x.compareTo ( Q.minL ) < 0 ) Q.minL = x ; }​​​​​​​​​​​​​​​public static Element Minimum ( Queap Q ) { // t เป็นต้นไม้ 2-4 และ x0, cv เป็นโหนดของต้นไม้ถ้า( Q . minL . compareTo ( Q . t . x0 . cv . key ) < 0 ) return Q . minL ;คืนค่าQ.t.x0.cv.key ; }​​​​​​​public static void Delete ( Queap Q , QueapNode x ) { Q . t . deleteLeaf ( x ); -- Q . n ; -- Q . k ; }public static void Delete ( Queap Q , Element x ) { QueapNode n ; if ( x . inList ) { // ตั้งค่า inList ของทุกองค์ประกอบในรายการเป็น false n = Q . t . insertList ( Q . l , x ); Q . k = Q . n ; Delete ( Q , n ); } else if (( n = Q . t . x0 . cv ). key == x ) Delete ( Q , n ); }public static Element DeleteMin ( Queue Q ) { Element min = Minimum ( Q ); Delete ( Q , min ); return min ; } }

• คิว (โครงสร้างข้อมูล)
• ต้นไม้แผ่กว้าง