User Tools

Site Tools


Sidebar

1. บทนำ

2. การวิเคราะห์ Algorithm

3. List, Stack and Queue

4. Tree

5. Hashing

6. Priority Queues

7. การจัดเรียง (Sorting)

8. The Disjoint Set

9. Graph Algorithms

dsa:pqbinomialq

6.8 Binomial Queues

ถึงแม้ว่าทั้ง leftish และ skew heaps จะสนับสนุนการดำเนินงานการควบรวบ การบรรจุ และการลบ deleteMin ที่มีประสิทธิภาพด้วยเวลาทำงานเป็น $O(log\ N)$ ต่อการทำงานหนึ่งครั้ง แต่ยังมีส่วนที่สามารถปรับปรุงได้เนื่องจากเราทราบว่า binary heap สนับสนุนการทำงานการบรรจุค่าด้วยเวลาเฉลี่ยเป็นค่าคงที่ต่อการทำงาน 1 ครั้ง โครงสร้างข้อมูล Binomial queues สนับสนุนการดำเนินการทั้ง 3 อย่างในกรณี worst-case ด้วยเวลา $O(log\ N)$ ต่อหนึ่งการดำเนินการ แต่สนับสนุนการการบรรจุที่ใช้เวลาคงที่ในกรณีเฉลี่ย

6.8.1 Binomial Queue Structure

Binomial queues แตกต่างจากโครงสร้าง priority queues ที่ได้กล่าวมาในหัวข้อก่อน ๆ กล่าวคือ binomial queue ไม่ได้เป็น heap-ordered tree แต่ binomial queue เป็นกลุ่มของทรีที่เป็น heap-ordered trees ซึ่งเราจะเรียกว่า forest โดยที่ทรีที่เป็น heap-ordered trees แต่ละทรีต้องมีรูปแบบเป็นไปตามข้อกำหนดของ binomial tree กล่าวคือ binomial queue หนึ่งสามารถมี binomial tree ที่มีความสูงของทรี (height) หนึ่ง ๆ ได้เพียงหนึ่ง binomial tree เท่านั้น binomial tree ที่มี height = 0 เป็นทรีที่มีโนดเพียงหนึ่งโนด; binomial tree, $B_k$, คือทรีที่มีความสูง = k จะเกิดจากการนำ binomial tree, $B_{k-1}$ มาเชื่อมต่อกับรากของ binomial tree $B_{k-1}$ อีกตัวหนึ่ง รูปที่ 6.28 แสดง binomial trees $B_0, B_1, B_2, B_3$, และ $B_4$

จากรูปจะเห็นได้ว่า binomial tree $B_k$ ประกอบด้วยรากที่ลูกเป็น $B_0, B_1, . . ., B_k-1$ Binomial trees ที่มีความสูง k มีโนดจำนวนทั้งสิ้น $2^k$ โนด และจำนวนโนดในระดับความลึก d ก็คือค่าของ binomial coefficient $k\choose d$ ซึ่งก็คือ $\frac{k!}{(d!(k-d)!)}$ ถ้ากำหนดให้ทรีเหล่านี้ต้องดำรงไว้ซึ่ง heap ordered และให้ทรีที่มีความสูงหนึ่งค่ามีได้เพียงทรีเดียวด้วยแล้วเราก็จะสามารถใช้กลุ่มของ binomial tree นี้แทน priority queue ที่ขนาดใด ๆ ที่แตกต่างกันได้เสมอ เช่น priority queue ขนาด 13 โนด สามารถเขียนแสดงได้ด้วยกลุ่ม binomial tree $B_3, B_2, B_0$ และเราสามารถเขียนแทนมันได้ด้วยไบนารี 1101 โดยจะเห็นว่ามันไม่เพียงแต่แสดงค่า 13 ด้วยเลขฐาน 2 เท่านั้น แต่บิตที่เป็น 1 ยังได้แสดงให้เห็นด้วยว่ามีทรีตามตำแหน่ง significant bits อยู่ด้วย และในกรณีนี้คือ บิต 0, 2, และ 3 ที่หมายความว่า priority queue นี้ประกอบด้วย binomial tree $B_3, B_2, B_0$ รูปที่ 6.29 แสดง priority queue ที่มีจำนวนสมาชิก 6 ค่าด้วย binomial tree 2 ตัว

รูปที่ 6.28 Binomial trees $B_0, B_1, B_2, B_3,$ และ $B_4$

รูปที่ 6.29 Binomial trees H1 ที่มีสมาชิก 6 ตัว

6.8.2 การดำเนินการของ Binomial Queue

เราสามารถค้นหาสมาชิกที่มีค่าน้อยที่สุดได้ด้วยการ scan ที่โนดรากของทุก ๆ ทรี เนื่องจากจำนวนทรีที่แตกต่างกันจะมีได้สูงสุด คือ log(N) ทรีด้วยกัน ดังนั้น การหาค่าต่ำสุดจึงใช้เวลาเป็น O(log N) หรือในกรณีที่เราเก็บสารสนเทศของค่าต่ำสุดเอาไว้ด้วย (เช่นตำแหน่งของมัน) เราก็ใช้เวลาในการค้นหาเป็น O(1) แต่นั่นเราต้องไม่ลืมปรับปรุงสารสนเทศนี้เมื่อมีการเปลี่ยนแปลงอันเนื่องมาจากการดำเนินการอื่น ๆ ด้วย การควบรวม binomial queues 2 ตัว ไม่มีความยุ่งยากใด ๆ ซึ่งจะแสดงวิธีการด้วยตัวอย่างต่อไปนี้ คือ มี binomial queues, H1 และ H2 มีสมาชิก 6 และ 7 ตัวตามลำดับ ตามรูปที่ 6.30

ให้ H3 เป็น binomial queue ตัวใหม่ เนื่องจาก H1 ไม่มี binomial tree ที่มีความสูง 0 แต่ H2 มี ดังนั้น เราเพียงใช้ binomial tree ที่ความสูง 0 ใน H2 เป็นส่วนหนึ่งของ H3 จากนั้นทำการควบรวม binomial trees ที่มีความสูง 1 เข้าด้วยกันโดยที่ทั้ง H1 และ H2 ต่างก็มี binomial trees ที่มีความสูง 1 ดังนั้น เราจึงควบรวมมันเข้าด้วยกันได้โดยใช้ทรีตัวที่มีค่าที่โนดรากมากกว่าไปเป็นทรีย่อยของตัวที่มีค่าที่โนดรากน้อยกว่า ทำให้ได้ binomial tree ที่มีความสูง 2 ดังรูปที่ 6.31 ดังนั้น H3 ก็จะไม่มี binomial tree ที่มีความสูง 1 อยู่ด้วย ในขณะนี้จะมี binomial tree ที่มีความสูงเท่ากับ 2 อยู่ 3 ทรีด้วยกัน คือ ทรีเดิม H1 และ H2 และอีกหนึ่งทรีที่เกิดขึ้นใหม่จากขั้นตอนการทำงานที่ผ่านมา เราจะเก็บ binomial tree ที่มีความสูงเท่ากับ 2 หนึ่งทรีเอาไว้ใน H3 และควบรวบทรีอีก 2 ทรีทีเหลือซึ่งจะเกิดทรีใหม่ที่มีความสูงเท่ากับ 3 เนื่องจากทั้ง H1 และ H2 ไม่มีทรีที่มีความสูงเป็น 3 เลย ดังนั้นทรีที่ได้จากการควบรวมนี้จึงถูกนำไปเป็นทรีหนึ่งใน H3 ผลลัพธ์ของ binomial queue ที่ได้จากการทำงานที่กล่าวมานี้แสดงอยู่ในรูปที่ 6.32

รูปที่ 6.30 Binomial queues, H1 และ H2

เนื่องจากการควบรวม binomial trees 2 ตัวนั้นใช้เวลาเป็น constant time และจำนวน binomial trees ในแต่ละ binomial queue นั้นมีจำนวนเท่ากับ $O(log\ N)$ ดังนั้นการควบรวมในกรณี worst-case จึงใช้เวลาเป็น $O(log\ N)$ ถ้าต้องการให้การดำเนินการนี้มีประสิทธิภาพขึ้นเราจะต้องจัดให้ทรีใน binomial queue มีการจัดเรียงลำดับตามค่าความสูงของทรี

รูปที่ 6.31 ควบรวม binomial trees H1 และ H2 ที่มีความสูง 1 เข้าด้วยกัน

รูปที่ 6.32 Binomial queues, H3 จากการควบรวม Binomial queues, H1 และ H2

การบรรจุสมาชิกใหม่เข้าใน binomial queue เป็นเพียงกรณีพิเศษชองการควบรวมเท่านั้น ซึ่งก็คือการสร้างทรีที่มีโนดหนึ่งโนดขึ้นมา (คือสร้างจากสมาชิกตัวใหม่นั้น) แล้วทำการควบรวมกับทรีเดิมที่เราต้องการบรรจุค่าใหม่นั้นลงไป และด้วยวิธีการเดียวกับที่กล่าวมาแล้วข้างบน เวลาที่ใช้ในกรณี worst-case สำหรับการดำเนินการนี้ คือ $O(log\ N)$ ถ้าจะกล่าวให้ถูกต้องยิ่งขึ้น กล่าวสำหรับ priority queue ที่เราจะบรรจุค่าใหม่นั้น ถ้ามันมีคุณสมบัติที่ binomial tree ที่มีความสูงน้อยที่สุดที่ไม่มีอยู่ใน priority queue นั้นคือ $B_i$ แล้ว running time ของการดำเนินการนี้ก็จะแปรผันตามค่า i + 1 เช่น H3 ในรูปที่ 6.38 binomial tree ที่มีความสูงน้อยที่สุดที่ไม่มีอยู่ใน priority queue นั้นคือ $B_1$ ดังนั้นการบรรจุค่าใหม่ก็จะเสร็จสิ้นใน 2 ขั้นตอนเท่านั้น เนื่องจากทรีแต่ละทรีมีค่าความเป็นไปได้ที่จะมีหรือไม่มีอยู่ใน binomial queue คือมีค่าความน่าจะเป็นคือ 1/2 ดังนั้นค่าคาดหวังที่การบรรจุจะทำได้เสร็จสิ้นใน 2 ขั้นตอน และดังนั้นเวลาเฉลี่ยของการทำงานจึงเป็นค่าคงที่ ยิ่งไปกว่านั้น การบรรจุข้อมูลจำนวน N ตัวลงในทรีว่างเริ่มแรกของ binomial queue ก็จะมี worst-case time เป็น $O(N)$

รูปที่ 6.33 แสดงการบรรจุค่า 1 ถึง 7 ตามลำดับลงใน binomial queue ว่าง ในขณะเมื่อทำการบรรจุค่า 4 นั้นเราต้องทำงานมากขึ้นกว่าการบรรจุค่าก่อนหน้ามัน โดยต้องทำการควบรวม 4 เข้ากับ $B_0$ ซึ่งจะได้ทรีใหม่ที่มีความสูงเท่ากับ 1 และควบรวมทรีใหม่ที่ได้นี้เข้ากับ $B_1$ ของทรีเดิมทำให้ได้ทรีที่มีความสูง 2 ซึ่งเป็น priority queue ใหม่ การทำงานนี้นับได้จำนวน 3 ขั้นตอนด้วยกัน คือ การควบรวม 2 ครั้งบวกกับอีก 1 ขั้นตอนการจบการทำงาน

รูปที่ 6.33 การบรรจุ 1 - 7

การดำเนินการ deleteMin เริ่มด้วยการค้นหา binomial tree ที่มีโนดรากที่มีค่าน้อยที่สุด และให้ tree ตัวนี้คือ Bk และ priority queue ตัวเริ่มต้น คือ H ให้ทำการย้าย binomial tree Bk ออกจากการเป็นทรีสมาชิกใน forest ของ H ซึ่งที่เหลือก็จะเป็น binomial queue ใหม่และเรียกมันว่า H' จากนั้นทำการลบโนดรากของ Bk ทำให้ทรีนี้แยกออกเป็นทรีย่อย คือได้เป็น binomial trees $B_0, B_1, ... , B_{k-l}$ ซึ่งกลุ่มทรีนี้ก็จะเป็น priority queue ใหม่เราจะเรียกว่า H“ จะเห็นว่าขณะนี้เรามี 2 binomial queue คือ H' และ H” และจะจบการทำงานด้วยการควบรวม H' และ H“ เข้าด้วยกันเป็น binomial queue สุดท้าย ดังรูปที่ 6.34 การทำงานของ deleteMin เริ่มด้วยการค้นหา binomial tree ที่มีค่าของโนดรากย้อยที่สุดด้วยเวลาเป็น $O(log\ N)$ และแยกทรีนี้ออกเป็น 2 binomial queues คือ H' และ H” จากนั้นทำการควบรวม queues ทั้งสองด้วยเวลาเป็น $O(log\ N)$ ดังนั้น deleteMin จึงมี running time เป็น $O(log\ N)$

รูปที่ 6.34 การทำงาน deleteMin ใน H3

6.8.3การสร้าง Binomial Queues

เพื่อให้การทำงาน deleteMin สามารถค้นหารากของทรีย่อยได้อย่างรวดเร็วจึงจำเป็นต้องใช้รูปแบบทั่วไปของทรี ทรีลูกของแต่ละโนดถูกจัดเก็บอยู่ใน linked list และแต่ละโนดจะมี reference ที่อ้างอิงถึงลูกตัวแรก (ถ้ามี) และยังต้องมีการจัดเรียงลำดับทรีลูกของมันตามขนาดของทรีลูกเองด้วย เรายังต้องมั่นใจด้วยว่ารูปแบบที่ใช้นี้จะเอื้อประโยชน์ในการควบรวมทรี 2 ตัวเข้าด้วยกัน เมื่อมีการควบรวมก็จะเป็นการนำทรีหนึ่งไปรวมเข้ากับอีกทรีหนึ่งและทรีใหม่ที่ได้นี้จะเป็นทรีย่อยที่มีขนาดใหญ่ที่สุด ดังนั้นเราจะจัดให้มีการเรียงลำดับทรีย่อยตามขนาดจากมากไปน้อย และเพื่อให้การควบรวม binomial queue 2 ตัวทำได้อย่างมีประสิทธิภาพ เราจะจัดเก็บ binomial queue ในรูปของอะเรย์ของ binomial tree

กล่าวโดยสรุป คือแต่ละโนดใน binomial tree หนึ่ง ๆ ประกอบด้วย ข้อมูล (data), ลูกตัวแรก (first child), และ right sibling ซึ่งทรีลูกในแต่ละ binomial tree เองก็ถูกจัดเรียงลำดับจากขนาดมากไปน้อย

รูปที่ 6.35 แสดง binomial queue ของรูปที่ 6.32 รูปที่ 6.36 แสดงการประกาศ type สำหรับโนดใน binomial tree และแสดงโครงร่างคลาสของ binomial queue

ในการควบรวม binomial queues 2 ตัวเข้าด้วยกันนั้น เราต้องใช้ฟังก์ชันเพื่อควบรวม binomial trees 2 ตัวที่มีขนาดเท่ากัน รูปที่ 6.37 แสดงการเปลี่ยนแปลงที่เกิดขึ้นกับ links เมื่อมีการควบรวม binomial trees 2 ตัว และโปรแกรมการทำงานแสดงในรูปที่ 6.38

รูปที่ 6.39 แสดงฟังก์ชัน merge โดยมี object ขณะนั้น ๆ (current object) เป็นตัวแทนของ H1 และมี rhs เป็นตัวแทนของ H2 โดยจะรวม H1 และ H2 แล้วเก็บผลไว้ใน H1 แล้วทำให้ H2 เป็นทรีว่าง ขณะระหว่างการทำงานที่ทรีที่มีอันดับ i จะมี t1 และ t2 เป็นทรีใน H1 และ H2 ตามลำดับ และมี carry เป็นทรีที่ได้จากการทำงานในขั้นตอนก่อนหน้า (อาจเป็น null) ผลการทำงานขึ้นอยู่กับกรณีต่าง ๆ ที่เป็นไปได้ 8 กรณี รูปที่ 6.40 แสดงฟังก์ชัน deleteMin สำหรับ Binomial queue

รูปที่ 6.35 รูปแบบที่ใช้แทน Binomial queue H3(รูปที่ 6.32)

class BinomialNode 
{     // Constructors
    BinomialNode ( Comparable theElement )  
	    {this( theElement, null, null );   }
    BinomialNode ( Comparable theElement,BinomialNode lt,BinomialNode nt )
    {   element     = theElement;
        leftChild   = lt; nextSibling = nt;
    }
    Comparable   element;     		// The data in the node
    BinomialNode leftChild;   		// Left child
    BinomialNode nextSibling; 		// Right child
} 
public class BinomialQueue 
{   public BinomialQueue( )
    {  theTrees = new BinomialNode[ MAX_TREES ];
       makeEmpty( );
    }
    public void merge( BinomialQueue rhs ) throws Overflow   
	  { /*Figure 6.55*/ }
    private static BinomialNode combineTrees ( BinomialNode t1, BinomialNode t2 )  { /*Figure 6.54*/ }
    public void insert( Comparable x ) throws Overflow
    {   BinomialQueue oneItem = new BinomialQueue( );
        oneItem.currentSize = 1;
        oneItem.theTrees[ 0 ] = new BinomialNode( x );
        merge( oneItem );
    }
    public Comparable findMin( )
    {   if( isEmpty( ) ) return null;
           return theTrees[ findMinIndex( ) ].element;
    }
    private int findMinIndex( )    { Figure 6.56 }
    public Comparable deleteMin( )   { Figure 6.56 }
    public boolean isEmpty( )   {  return currentSize == 0;   }
    public boolean isFull( )  {  return currentSize == capacity( );  }
    public void makeEmpty( )
    {   currentSize = 0;
        for( int i = 0; i < theTrees.length; i++ )
            theTrees[ i ] = null;
    }
    private static final int MAX_TREES = 14;
    private int currentSize;           // # items in priority queue
    private BinomialNode [ ] theTrees; // An array of tree roots
    private int capacity( ) {  return ( 1 << theTrees.length ) - 1;}
    public static void main( String [ ] args ) { /*Figure 6.57*/ }   	
 } 

รูปที่ 6.36 โครงร่างของคลาส Binomial queue และนิยามของโนด

รูปที่ 6.37 การควบรวม Binomial tree 2 ตัว

private static BinomialNode combineTrees( BinomialNode t1,  
							BinomialNode t2 )
{
    if( t1.element.compareTo( t2.element ) > 0 )
        return combineTrees( t2, t1 );
    t2.nextSibling = t1.leftChild;
    t1.leftChild = t2;
    return t1;
}

รูปที่ 6.38 ฟังก์ชันการควบรวมทรีที่มีขนาดกัน

public void merge( BinomialQueue rhs ) throws Overflow
{     
    if( this == rhs )    // Avoid aliasing problems
        return;
    if( currentSize + rhs.currentSize > capacity( ) )
        throw new Overflow( );
    currentSize += rhs.currentSize;
    BinomialNode carry = null;
    for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )
    {   
        BinomialNode t1 = theTrees[ i ];
        BinomialNode t2 = rhs.theTrees[ i ];
        int whichCase = t1 == null ? 0 : 1;
        whichCase += t2 == null ? 0 : 2;
        whichCase += carry == null ? 0 : 4; 
        switch( whichCase )
        {   case 0: /* No trees */
            case 1: /* Only this */
                   break;
            case 2: /* Only rhs */
                   theTrees[ i ] = t2;
                   rhs.theTrees[ i ] = null;  
	               break;
            case 4: /* Only carry */
                   theTrees[ i ] = carry;
                   carry = null;   
                   break;
            case 3: /* this and rhs */
                   carry = combineTrees( t1, t2 );
                   theTrees[ i ] = rhs.theTrees[ i ] = null; 
                   break;
            case 5: /* this and carry */
                   carry = combineTrees( t1, carry );
                   theTrees[ i ] = null;   
                   break;
            case 6: /* rhs and carry */
                   carry = combineTrees( t2, carry );
                   rhs.theTrees[ i ] = null;   
                   break;
            case 7: /* All three */
                   theTrees[ i ] = carry;
                   carry = combineTrees( t1, t2 );
                   rhs.theTrees[ i ] = null;   
                   break;
        }
    }
    for( int k = 0; k < rhs.theTrees.length; k++ )
        rhs.theTrees[ k ] = null;
    rhs.currentSize = 0;
}

รูปที่ 6.39 ฟังก์ชันการควบรวม 2 priority queues

public Comparable deleteMin( )
{  
    if( isEmpty( ) )  return null;
    int minIndex = findMinIndex( );
    Comparable minItem = theTrees[ minIndex ].element;
    BinomialNode deletedTree = theTrees[ minIndex ].leftChild;
    BinomialQueue deletedQueue = new BinomialQueue( );
    deletedQueue.currentSize = ( 1 << minIndex ) - 1;
    for( int j = minIndex - 1; j >= 0; j-- )
    {   deletedQueue.theTrees[ j ] = deletedTree;
        deletedTree = deletedTree.nextSibling;
        deletedQueue.theTrees[ j ].nextSibling = null;
    }
    theTrees[ minIndex ] = null;
    currentSize -= deletedQueue.currentSize + 1;
    try    { merge( deletedQueue ); }
    catch( Overflow e ) { }
    return minItem;
} 
private int findMinIndex( )
{
    int i;
    int minIndex;
    for( i = 0; theTrees[ i ] == null; i++ )
        ;
    for ( minIndex = i; i < theTrees.length; i++ )
        if ( theTrees[ i ] != null &&
          theTrees[ i ].element.compareTo( theTrees[ minIndex ].element ) < 0 )
          minIndex = i;
    return minIndex;
}

รูปที่ 6.40 deleteMin และ findMinIndex

public static void main( String [ ] args )
    {   
        int numItems = 10000;
        BinomialQueue h  = new BinomialQueue( );
        BinomialQueue h1 = new BinomialQueue( );
        int i = 37;
        System.out.println( "Starting check." );
        try
        { 
      	for ( i = 37; i != 0; i = ( i + 37 ) % numItems )
         	if ( i % 2 == 0 )  h1.insert( new MyInteger( i ) );
          	else  h.insert( new MyInteger( i ) );
     	    h.merge( h1 );
     	for ( i = 1; i < numItems; i++ )
            if ( ( (MyInteger) ( h.deleteMin( ) ) ).intValue( ) != i )    
            system.out.println( "Oops! " + i );
    	}   		// try block
    	catch ( Overflow e ) {   
		    System.out.println( "Unexpected overflow" );  
		} 
        System.out.println( "Check done." );
  	}   	
 }

รูปที่ 6.57 ฟังก์ชัน main

dsa/pqbinomialq.txt · Last modified: 2021/09/08 21:53 by wasu

Page Tools