CoE KKU

เป็นเรื่องที่ยากมากที่จะออกแบบโครงสร้างข้อมูลที่สนับสนุนการทำงานการควบรวมได้อย่างมีประสิทธิภาพ (ที่ใช้เวลาการควบรวมเป็น $o(N)$ ) ด้วยการใช้อะเรย์ดังเช่นที่ใช้ใน binary heap เนื่องจากดูเหมือนว่าการควบรวมจะต้องใช้การคัดลอกข้อมูลของอะเรย์หนึ่งไปยังอีกอะเรย์หนึ่งซึ่งต้องใช้เวลาเป็น $\Theta(N)$ สำหรับ heap ที่มีขนาดเท่ากัน ด้วยเหตุนี้ โครงสร้างข้อมูลชนิดก้าวหน้าทั้งหลายที่สนับสนุนการควบรวมจึงจำเป็นต้องใช้โครงสร้างที่ใช้ตัวเชื่อม (link structure) ในทางปฏิบัติก็จะทำให้การดำเนินการอื่น ๆ ช้าลง

เช่นเดียวกันกับ binary heap โครงสร้าง leftist heap ก็มีข้อกำหนด structural property และ ordering property ความจริงแล้วก็เช่นเดียว heap อื่น ๆ คือ โครงสร้าง leftist heap มีข้อกำหนดของ heap order property เป็นแบบเดียวกับ heap อื่น ๆ และยิ่งไปกว่านั้น leftist heap เป็น binary tree ส่วนที่ต่างกันคือ leftist heaps ไม่เป็น perfect balanced แต่กลับจะมีลักษณะที่ไม่สมดุลมาก

เราจะกำหนดนิยามของ null path length, npl(X) ของโนด X ใด ๆ เป็นความยาว (length) ของเส้นทางที่สั้นที่สุดจากโนด X ไปยังโนดที่มีลูกไม่เกินหนึ่งโนด ดังนั้น npl ของโนดที่ไม่มีโนดลูกหรือมีลูกหนึ่งโนด คือ 0 และกำหนดให้ npl(NULL) = –1 รูปที่ 6.20 แสดง null path lengths ของโนดในทรี

ข้อสังเกตก็คือ npl ของโนดใด ๆ จะมีค่ามากกว่าค่า npl ที่น้อยที่สุดของโนดลูกของมันอยู่ 1 ลักษณะดังที่กล่าวนี้ยังคงเป็นจริงสำหรับโนดที่มีโนดลูกน้อยกว่า 2 โนดเนื่องจาก npl ของ null มีค่าเป็น -1

คุณสมบัติของ leftist heap คือ ทุก ๆ โนด X ใน heap ต้องมีโนดลูกซ้าย (left child) ที่มีค่า null path length ต่ำสุดได้เท่ากับหรือมากกว่า null path length ของโนดลูกขวา (right child) ของมัน ทรีด้านซ้ายในรูปที่ 6.20 เท่านั้นที่มีคุณสมบัตินี้ คุณสมบัติดังกล่าวนี้ทำให้ทรีนี้เป็นทรีที่ไม่สมดุลและมีแนวโน้มที่จะเอนเอียงไปทางด้านซ้ายมากขึ้น และความจริงก็อาจจะเป็นไปได้ที่ทรีนี้ประกอบเส้นทางทางด้านซ้ายที่ยาวมาก จึงเรียกทรีนี้ว่า leftist heap

เนื่องจาก leftist heap มีความโน้มเอียงที่เส้นทางด้านซ้ายจะลงลึกได้มาก นั่นหมายความว่าเส้นทางด้านขวาก็จะสั้นกว่า ซึ่งความจริงแล้วเส้นทางด้านขวาของ leftist heap จะมีระยะที่สั้นกว่าเสมอ

ทฤษฎี 6.2 leftist tree ที่มีโนดเป็นจำนวน r โนดในเส้นทางขวา (right path) จะมีจำนวนโนดของทรีอย่างน้อย $2^r – 1$ โนด

พิสูจน์:

พิสูจน์โดยวิธี induction คือ ถ้า r = 1 ก็จะมีโนดของทรีอย่างน้อย 1 โนด ถ้าให้ทฤษฎีเป็นจริงสำหรับ 1, 2, . . ., r พิจารณา leftist tree ที่มี r + 1 โนดในเส้นทางขวา นั่นคือ รากของมันจะมีโนดอยู่ในทรีย่อยขวา (right subtree) อยู่จำนวน r โนดบนเส้นทางขวา และทรีย่อยซ้าย (left subtree) มีโนดอย่างน้อย r โนดอยู่บนเส้นทางขวา (right path) ของมัน (มิฉะนั้นแล้วมันจะไม่สามารถเป็น leftist ได้) ใช้ inductive hypothesis กับทรีย่อยที่กล่าวเหล่านี้ จะได้ว่ามันต้องมีโนดอย่างน้อย $2^r – 1$ โนดในแต่ละทรีย่อย และเมื่อรวมกับโนดที่รากจะได้โนดทั้งหมดอย่างน้อย $2^r+1 – 1$ โนดใน tree $( (2^r – 1) + (2^r – 1 ) + 1 = 2^r+1 – 1 )$ ซึ่งเป็นการพิสูจน์

การดำเนินการพื้นฐานของ leftist heaps คือ การควบรวมทรี (merging) การบรรจุค่าลงในทรี leftist heaps ก็เป็นกรณีพิเศษของการควบรวมซึ่งพิจารณาได้ว่าการบรรจุค่าคือการควมรวม leftist heaps ที่มีโนด 1 โนด เข้ากับอีก heap หนึ่งที่มีขนาดใหญ่กว่านั่นเอง ในตอนแรกจะกล่าวถึงการใช้การแก้ปัญหาแบบ recursive จากนั้นจึงจะแสดงการใช้วิธีแบบ nonrecursive อินพุตที่ใช้เป็น leftist heaps 2 ตัว คือ H1 และ H2, ตามรูปที่ 6.21 จะเห็นว่าค่าที่น้อยที่สุดอยู่ที่รากของทรี ในรายการของโนดแต่ละโนดนั้นนอกจากต้องใช้พื้นที่เพื่อเก็บข้อมูลค่า และ left และ right references แล้ว ในโนดยังต้องเก็บค่า null path length ด้วย

ถ้ามี heap ตัวหนึ่งเป็น heap ว่าง เราก็ให้ค่ากลับเป็นอีก heap หนึ่ง ถ้าไม่เป็นเช่นนี้ ก็ให้ควบรวม heap ทั้งสองเข้าด้วยกัน ด้วยการเปรียบเทียบค่าของราก และทำการควบรวมแบบ recursive ด้วยการใช้ heap ที่มีค่ารากมากกว่าไปควบรวมเข้ากับ right subheap ของ heap ที่มีค่ารากน้อยกว่า ใน heap ตัวอย่าง เราจะควบรวมแบบ recursive H2 เข้ากับ subheap ของ H1 ที่มีรากเป็น 8 ทำให้ได้ heap ในรูปที่ 6.21 ขั้นตอนที่ 1 เนื่องจากทรีนี้เกิดขึ้นจากการทำงานแบบ recursive จึงเชื่อได้ว่าผลที่ได้จะเป็น leftist heap จากนั้นก็ใช้ heap ใหม่ที่ได้นี้เป็น right child ของรากของ H1

แม้ว่า heap ที่ได้จะสอดคล้องกับ heap order property ก็ตาม มันยังคงไม่เป็น leftist เนื่องจาก left subtree ของโนดรากมีค่า npl = 1 ขณะที่ right subtree มี npl = 2 นั่นคือ มันเสียคุณสมบัติของ leftist เนื่องจากโนดรากของมัน อย่างไรก็ตาม ส่วนที่เหลือของ tree เป็น leftist ทรีย่อยขวาของโนดรากเป็น leftist เนื่องจากการทำงานตามขั้นตอน recursive step ที่ใช้ และ left subtree ของรากไม่มีการเปลี่ยนแปลงใด ๆ เกิดขึ้นในระหว่างขั้นตอนการทำงาน ดังนั้นมันยังคงสถานะความเป็น leftist เช่นเดิม

ดังนั้น เราเพียงแต่แก้ไขที่รากของทรีเท่านั้น โดยเราสามารถทำให้ heap ทั้งหมดเป็น leftist ได้โดยการสลับทรีย่อยซ้ายกับทรีย่อยขวาของโนดราก (swap child ในรูป 6.21) และทำการปรับปรุงค่า null path length – คือ ค่าใหม่ของ null path length เท่ากับ 1 บวกด้วย null path length ของลูกตัวขวาตัวใหม่ — เป็นอันเสร็จสิ้นการควบรวม จะเห็นได้ว่าถ้าไม่มีการปรับปรุงค่า null path length ก็จะทำให้ค่า null path lengths ทั้งหมดเป็น 0 และ heap ที่ได้ก็จะไม่เป็น leftist

จากขั้นตอนการดำเนินการที่ได้กล่าวข้างบนนั้นสามารถนำไปเขียนโปรแกรมได้โดยตรง คลาสของโนด (รูปที่ 6.22) เหมือนกับคลาสของโนดใน binary tree ยกเว้นมีข้อมูลค่า npl (null path length) เพิ่มเติมเข้ามาในโนด ในทรีของ leftist heap ประกอบด้วยข้อมูลสมาชิก (data member) สำหรับเก็บค่าที่เป็น reference ที่ใช้ในการอ้างอิงไปที่รากของทรี การบรรจุสมาชิกใหม่ลงในทรีว่างจะทำให้เกิดการเปลี่ยนโนดที่จะถูกอ้างอิงโดยรากเช่นเดียวกับที่ได้กล่าวในบทที่ 4 โครงร่างของคลาสสำหรับ leftist heap แสดงในรูปที่ 6.22

ฟังก์ชัน merge 2 ฟังก์ชันดังแสดงในรูปที่ 6.23 ออกแบบมาให้ประกันว่ารากของ H1 มีค่าน้อยกว่าเสมอ และการควบรวมทรีเกิดขึ้นจริงในฟังก์ชัน merge1 (ดูรูปที่ 6.24) ฟังก์ชัน merge ที่เป็น public เป็นฟังก์ชันที่จะควบรวม rhs เข้าใน controlling heap และหลังจากนั้น rhs จะกลายเป็นทรีว่าง

class LeftHeapNode 
{   
   LeftHeapNode( Comparable theElement )
     {   this( theElement, null, null );   }
   LeftHeapNode( Comparable theElement, LeftHeapNode lt, LeftHeapNode rt )
    {   element = theElement;
        left = lt; right = rt; npl = 0;
    }
    Comparable   element;      	// The data in the node
    LeftHeapNode left;         	// Left child
    LeftHeapNode right;        	// Right child
    int          npl;          		// null path length
} 
 
public class LeftistHeap 
{   public LeftistHeap( ) { root = null; }
    public void merge( LeftistHeap rhs ) { /* Figure 6.26 */ }
    public void insert( Comparable x ) { /* Figure 6.29 */ }
    public Comparable findMin( )
    {  if( isEmpty( ) )
            return null;
        return root.element;
    }
    public Comparable deleteMin( ) { /* Figure 6.30 */ }
    public boolean isEmpty( ) { return root == null; }
    public boolean isFull( ) { return false; }
    public void makeEmpty( ) { root = null; } 
    private LeftHeapNode root;    		// root
    private static LeftHeapNode merge( LeftHeapNode h1, LeftHeapNode h2 )
      	{/* Figure 6.26 */}
    private static LeftHeapNode merge1( LeftHeapNode h1, LeftHeapNode h2 )
       	{/* Figure 6.27 */}
    private static void swapChildren( LeftHeapNode t )
    {   LeftHeapNode tmp = t.left;
        t.left = t.right;
        t.right = tmp;
    }
} 

รูปที่ 6.22 Leftist heap type declarations

เวลาที่ใช้ในการ merge แปรผันตามผลบวกของความยาวของ right paths เนื่องจากใช้การทำงานที่คงที่กับโนดแต่ละโนดระหว่าง recursive calls ดังนั้นจึงได้ขอบเขตเวลาเป็น O(log N)

ในการควบรวม leftist heap 2 ตัว เราสามารถดำเนินการตามที่กล่าวมานี้ด้วยวิธีแบบ nonrecursive ด้วยการทำงานเป็น 2 รอบด้วยกัน รอบแรกจะทำการสร้างทรีใหม่ด้วยการความรวบเส้นทางขวาของทรีทั้ง 2 นั้นโดยการจัดเรียงลำดับค่าของโนดในเส้นทางขวาของ H1 และ H2 โดยไม่แตะต้องลูกตัวซ้ายของมัน จากทรีตัวอย่างของเราจะได้ค่าโนดในเส้นทางขวาเป็น 3, 6, 7, 8, 18 ดังแสดงในรูปที่ 6.21 การทำงานในรอบที่สองเป็นการปรับแต่ง heap ด้วยการสลับทรีลูกของโนดที่ไม่เป็นไปตามข้อกำหนดของ leftist heap ซึ่งจากรูป 6.21 ต้องทำการสลับทรีลูกของโนด 7 และ 3 ก็จะได้ทรีสุดท้ายเช่นเดียวกับที่ผ่านมา วิธีการที่กล่าวนี้เห็นภาพได้ชัดเจนแต่เขียนโปรแกรมได้ยากกว่าวิธีแบบ recursive

ดังที่ได้กล่าวมาแล้ว การบรรจุค่าใหม่ลง leftist heap ได้ด้วยการนำค่าใหม่มาสร้างเป็น leftist heap ที่มี 1 โนด จากนั้นก็นำไปควบรวมกับ leftist heap ที่ต้องการบรรจุค่าลงไป การดำเนินการ deleteMin เป็นการลบโนดรากออกจากทรีซึ่งทำให้เกิดทรีใหม่ 2 ทรีจากทรีย่อยซ้ายและขวา และให้ควบรวมทรีทั้ง 2 นี้เข้าด้วยกันด้ววิธีการควบรวมเดิมที่กล่าวมา ดังนั้น deleteMin จึงใช้เวลาเป็น O(log N) รูปที่ 6.25 และ 6.26 แสดงฟังก์ชันทั้งสองที่กล่าวนี้

/* Merge rhs into the priority queue */
public void merge( LeftistHeap rhs )
{   if ( this == rhs )    // Avoid aliasing problems
           return;
    root = merge( root, rhs.root );
    rhs.root = null;
}
/* Method to merge two roots,  Deals with deviant cases and calls recursive merge1 */
private static LeftHeapNode  merge( LeftHeapNode h1, LeftHeapNode h2 )
{   if ( h1 == null )    return h2;
    if ( h2 == null )   return h1;
    if ( h1.element.compareTo( h2.element ) < 0 )
        return merge1( h1, h2 );
    else
        return merge1( h2, h1 );
}

รูปที่ 6.23 Driving routine สำหรับการควบรวม leftist heaps

/* Assumes trees are not empty, and h1's root contains smallest item. */
private static LeftHeapNode merge1( LeftHeapNode h1, LeftHeapNode h2 )
{
    if ( h1.left == null )   	// Single node
        h1.left = h2;       		// Other fields in h1 already accurate
    else
    {
        h1.right = merge( h1.right, h2 );
        if ( h1.left.npl < h1.right.npl )
            swapChildren( h1 );
        h1.npl = h1.right.npl + 1;
    }
    return h1;
}

รูปที่ 6.24 ฟังก์ชันที่เกิดการทำงานการควบรวมของ leftist heaps

/* Insert into the priority queue, maintaining heap order,
    x the item to be inserted */
public void insert( Comparable x )
{  root = merge( new LeftHeapNode( x ), root );   }

รูปที่ 6.25 ฟังก์ชันการบรรจุค่าลงใน leftist heap

public Comparable deleteMin( )
{   if( isEmpty( ) )
        return null;
    Comparable minItem = root.element;
    root = merge( root.left, root.right );
    return minItem;
}

รูปที่ 6.26 ฟังก์ชัน deleteMin ของ leftist heap