CoE KKU

Skew heaps เป็น binary trees ที่มีข้อกำหนดคุณสมบัติ heap order แต่ไม่มีข้อกำหนดคุณสมบัติทางโครงสร้าง Skew heaps ไม่มีสารสนเทศที่เกี่ยวกับ null path length ของโนด เส้นทางขวาของโนด (right path) ของ skew heap อาจจะยาวแค่ไหนก็ได้ ดังนั้น จึงอาจจะมี running time กรณี worst-case ของการดำเนินการใด ๆ เป็น $O(N)$ ได้ อย่างไรก็ตาม การดำเนินการที่ต่อเนื่องกัน $M$ ครั้ง ก็จะมี running time รวมในกรณี worst-case เป็น $O(M\ log\ N)$ ได้ ดังนั้น skew heaps จึงมี amortized cost/per operation เป็น $O(log\ N)$

การดำเนินการพื้นฐานใน skew heaps ก็เพื่อการควบรวม ในที่นี้จะแสดงโปรแกรมเพื่อการควบรวมที่เป็นแบบ recursive เช่นเดียวกับที่กล่าวมาในหัวข้อที่แล้ว ข้อแตกต่างจากการทำงานใน leftist heaps คือ สำหรับการควบรวมของทรี skew heaps เราจะสลับระหว่างทรีย่อยซ้ายและทรีย่อยขวาเสมอโดยไม่มีเงื่อนไขเมื่อมีการควบรวมเกิดขึ้น ยกเว้นโนดที่มีค่ามากที่สุดที่อยู่ในเส้นทางขวาเนื่องจากมันไม่มีโนดลูก พิจารณาตัวอย่างของ heap 2 ตัวดังในตัวอย่างที่แล้ว ถ้าเราทำการควบรวม H2 แบบ recursive เข้ากับทรีย่อย (subheap) ของ H1 ดังแสดงในรูปที่ 6.27