CoE KKU

ในบทที่ 6 ได้กล่าวแล้วว่าเราอาจใช้ priority queues ในการจัดเรียงด้วยเวลา O(N log N) อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึมอื่น ๆ ที่กล่าวมาแล้ว อย่างไรก็ตาม ในทางปฏิบัติแล้วมันทำงานช้ากว่า shellsort ที่ใช้ลำดับการเพิ่มของ Sedwick

วิธีการที่ใช้ตามที่กล่าวในบทที่ 6 คือ สร้าง binary heap (มีสมาชิก N ตัว) ซึ่งใช้เวลาเป็น O(N) จากนั้นทำ deleteMin N ครั้ง สมาชิกที่ถูกย้ายออกไปจาก heap ตัวแรก คือตัวที่มีค่าน้อยที่สุด และเรียงลำดับตามค่าไป แล้วนำไปเก็บในอะเรย์อีกตัวหนึ่งจากนั้นก็คัดลอกกลับไปยังอะเรย์เดิมซึ่งก็จะเป็นคำตอบในการจัดเรียง เนื่องจากการทำ deleteMin แต่ละตัวใช้ O(log N) ดังนั้น running time รวมทั้งหมด คือ O(N log N)

ปัญหาของอัลริทึมนี้ คือ ต้องใช้อะเรย์เพิ่มเข้ามาสำหรับเก็บค่าที่ deleteMin ออกไปจาก heap นั่นคือต้องใช้พื้นที่หน่วยความจำเพิ่มขึ้นเป็นสองเท่า และอาจก่อปัญหาได้ในบางกรณี ส่วนเวลาที่ใช้ในการคัดลอกอะเรย์กลับไปยังอะเรย์แรกนั้นใช้เวลาเป็น O(N) ซึ่งไม่มีผลอย่างมีนัยสำคัญต่อ running time เพื่อหลีกเลี่ยงการใช้อะเรย์ตัวที่สองดังกล่าว เราพบว่าหลังจากการ deleteMin แต่ละครั้งนั้นขนาดของ heap ก็จะลดลง 1 ตัวด้วย ดังนั้นตำแหน่งเซลล์ใน heap ที่ว่างซึ่งเป็นตำแหน่งสุดท้ายใน heap เดิมนั้นก็สามารถนำมาใช้ในการเก็บค่าของตัวที่เพิ่งจะถูกย้ายออกไปนั้นได้ เช่น ถ้าเรามี heap ที่มีสมาชิก 6 ตัว การทำ deleteMin ครั้งแรกจะได้ a1 และทำให้ heap เหลือสมาชิก 5 ตัว ดังนั้นเราก็สามารถบรรจุ a1 ลงในตำแหน่งที่ 6 ที่ว่างนั้นได้ การ deleteMin ถัดมาได้ a2 และ heap จะมีสมาชิกเหลือเพียง 4 ตัว และเราสามารถบรรจุ a2 ลงในตำแหน่ง 5 ได้

ด้วยกรรมวิธีที่กล่าวมาข้างบนนี้ หลังการทำงาน deleteMin ครั้งสุดท้ายแล้ว เราจะได้อะเรย์ที่มีสมาชิกจัดเรียงค่าจากมากไปน้อย ดังนั้นถ้าเราต้องการจัดเรียงค่าจากน้อยไปมาก เราก็จะใช้วิธีการเดียวกันนี้เพียงแต่ต้องใช้ heap ที่ parent มีค่ามากกว่า child ของมัน นั่นคือ (max)heap ในที่นี้เราจะใช้ (max)heap ในการ implement ของเราและยังคงใช้อะเรย์เช่นเดิม ขั้นแรกสร้าง heap ด้วย linear time จากนั้นทำ deleteMax เป็นจำนวน N - 1 ครั้ง ด้วยการสลับสมาชิกตัวสุดท้ายใน heap กับสมาชิกตัวแรก แล้วลดขนาดของ heap ลงแล้วทำการ percolating down หลังจบอัลกอริทึมจะได้อะเรย์ที่มีสมาชิกเรียงตามลำดับค่า เช่นมีลำดับของค่าเริ่มต้นคือ 31, 41, 59, 26, 53, 58, 97 ซึ่งสร้าง heap ได้ดังรูปที่ 7.6 ภายหลังจากทำการ deleteMax ครั้งแรกแล้วก็จะได้สถานะของ heap และอะเรย์ดังรูปที่ 7.7 ซึ่งมีค่า 31 เป็นค่าสุดท้ายใน heap และ 97 ถูกบรรจุลงในตำแหน่งสุดท้ายของ heap ซึ่งในทางเทคนิกแล้วในขณะนี้ตำแหน่งดังกล่าวนี้ไม่ถือว่าเป็นส่วนหนึ่งของ heap อีกต่อไปแล้ว รูปที่ 7.8 เป็นโปรแกรม heapsort ซึ่งแตกต่างจาก binary heap เล็กน้อย คือ ในที่นี้จะใช้อะเรย์ตั้งแต่ตำแหน่ง 0 แต่สำหรับ binary heap เราใช้ตำแหน่งที่ 1 ของอะเรย์เป็นตำแหน่งแรก

รูปที่ 7.6 รูป Heap หลัง buildHeap

รูปที่ 7.7 รูป Heap หลังการ deleteMax ครั้งแรก  

/* Internal method for heapsort.
    return the index of the left child. */
private static int leftChild( int i )  
{  
    return 2 * i + 1;  
}
private static void percDown( Comparable [ ] a, int i, int n )
{           
        int child;
        Comparable tmp;
/* 1*/  for ( tmp = a[ i ]; leftChild( i ) < n; i = child )
        {
/* 2*/      child = leftChild( i );
/* 3*/      if (child != n - 1 && a[child].compareTo(a[ child + 1 ]) < 0 )
/* 4*/          child++;
/* 5*/      if ( tmp.compareTo( a[ child ] ) < 0 )
/* 6*/            a[ i ] = a[ child ];
            else
/* 7*/            break;
            }
/* 8*/      a[ i ] = tmp;
        } 
/*** Standard heapsort.
* @param a an array of Comparable items.
*/
        public static void heapsort( Comparable [ ] a )
        {
/* 1*/      for( int i = a.length / 2; i >= 0; i-- ) 	 /* buildHeap */
/* 2*/          percDown( a, i, a.length );
/* 3*/      for ( int i = a.length - 1; i > 0; i-- )
            {
/* 4*/          swapReferences( a, 0, i );            	/* deleteMax */
/* 5*/          percDown( a, 0, i );
            }
        }

รูปที่ 7.8 โปรแกรม heapsort