CoE KKU

โครงสร้างข้อมูลที่เราใช้สำหรับ priority queue คือ binary heaps และเรียกสั้น ๆ ว่า heaps ซึ่งเป็นวิธีทั่วไปที่นิยมใช้ โครงสร้าง heaps มีคุณสมบัติสองอย่างเช่นเดียวกับ binary search trees คือ คุณสมบัติทางโครงสร้าง (structure property) และ คุณสมบัติทางลำดับค่า (heap order property) และก็เช่นเดียวกับ AVL trees กล่าวคือ การดำเนินการกับ heap อาจจะทำลายคุณสมบัติอย่างใดอย่างหนึ่งของมัน ดังนั้น เมื่อมีการดำเนินการที่ว่านี้แล้วจะต้องทำการปรับปรุง heap ให้มีคุณสมบัติกลับคืนสู่สภาพของมัน

heap เป็น binary tree ที่มีการเติมเต็มที่สมบูรณ์ ยกเว้นในระดับล่างสุดของทรี และการเติมเต็มแต่ละระดับนั้นจะต้องทำจากซ้ายไปขวาของทรี ทรีที่มีคุณลักษณะนี้ เรียกว่า complete binary tree ดังแสดงในรูปที่ 6.2

คุณสมบัติหนึ่งของ complete binary tree ที่มีความสูง (height) เป็น $h$ คือ ทรีนั้นจะมีจำนวนโนดอยู่ระหว่าง $2^h$ ถึง $2^{h+1} - 1$ โนด นั่นคือความสูงของ complete binary tree คือ $⌊log\ n⌋$ ซึ่งก็คือ $O(log\ n)$

เนื่องจาก complete binary tree มีรูปแบบของโครงสร้างที่สม่ำเสมอ ดังนั้นเราสามารถใช้อะเรย์แทนมันได้โดยไม่จำเป็นต้องใช้ตัวเชื่อมข้อมูล รูปที่ 6.3 เป็นอะเรย์ที่ใช้แทน heap ในรูปที่ 6.2.

รูปที่ 6.3 อะเรย์ที่ใช้สำหรับ heap ในรูปที่ 6.2

สมาชิกของอะเรย์ที่ตำแหน่ง i ใดๆ (heap จะใช้ อะเรย์ตำแหน่งเริ่มต้นที่ 1) มีโนดลูกตัวซ้ายเป็นสมาชิกอยู่ที่เซลล์ตำแหน่ง 2i, และโนดลูกตัวขวาอยู่ที่เซลล์ถัดไป คือตำแหน่ง 2i + 1 และมีโนดแม่ (parent) เป็นสมาชิกของอะเรย์อยู่ที่เซลล์ตำแหน่ง ⌊i/2⌋ ดังนั้นการดำเนินการและการท่องไปในทรีจึงเป็นเรื่องง่ายและสามารถทำได้อย่างรวดเร็ว ปัญหาอย่างเดียวที่เหลือของการใช้วิธีนี้ คือ จะต้องประมาณการขนาดสูงสุดของ heap ล่วงหน้า แต่โดยทั่วไปก็ไม่เป็นปัญหาเนื่องจากสามารถปรับเปลี่ยนขนาดได้ตามความจำเป็น

ดังนั้นโครงสร้างข้อมูลของ heap จึงประกอบด้วยอะเรย์ของออปเจ็กต์ (ซึ่งเป็นออปเจ็กต์ Comparable) และเลขจำนวนเต็มแสดงจำนวนสมาชิกใน heap ณ เวลาหนึ่ง ๆ รูปที่ 6.4 แสดงโครงร่างคลาสของ priority queue รูปที่ 6.4a เป็นฟังก์ชัน constructors และ makeEmpty

ในบทนี้เราจะแสดงรูปของ heap ในรูปแบบของทรี โดยที่การใช้งานจริงคืออะเรย์ที่กล่าวมาแล้ว

public class BinaryHeap 
{   public BinaryHeap( ) { /* Figure 6.4a */ }
    public BinaryHeap( int capacity ) { /* Figure 6.4a */ }
    public void insert( Comparable x ) throws Overflow { /* Figure 6.8 */ }
    public Comparable findMin( )
        {   if( isEmpty( ) )
                return null;
             return array[ 1 ];
        }
    public Comparable deleteMin( ){ /* Figure 6.12 */ }
    public boolean isEmpty( ) { return currentSize == 0; } 
    public boolean isFull( )  { return currentSize == array.length - 1;}
    public void makeEmpty( ) { /* Figure 6.4a */ }
 
    private static final int DEFAULT_CAPACITY = 100;
    private int currentSize;    	     // Number of elements in heap
    private Comparable [ ] array; 	     // The heap array
    private void percolateDown( int hole ) { /* Figure 6.12 */ }
    private void buildHeap( )  { /* Figure 6.14 */ }
}

รูปที่ 6.4 โครงร่างคลาสของ priority queue

public BinaryHeap( )
{    this( DEFAULT_CAPACITY );  }
public BinaryHeap( int capacity )
{     currentSize = 0;
      array = new Comparable[ capacity + 1 ];
}
 
public void makeEmpty( )
{      currentSize = 0;    } 

รูปที่ 6.4a Constructor และ makeEmpty

คุณสมบัติที่ทำให้การดำเนินการต่าง ๆ ของ heap ทำงานอย่างรวดเร็วได้ก็คือคุณสมบัติทางลำดับค่า (heap order property) เนื่องจากเราต้องการค้นหาค่าที่น้อยที่สุดในโครงสร้างให้ได้อย่างรวดเร็วที่สุดดังนั้นจึงสมเหตุผลที่เราจะเอาสมาชิกที่มีค่าน้อยที่สุดมาไว้ตำแหน่งของโนดราก ถ้าเราถือว่าทุก ๆ ทรีย่อยต้องเป็น heap ด้วยก็หมายความว่าโนดใด ๆ ในทรีจะต้องมีค่าน้อยกว่าโนดด้านล่างของมัน

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

การดำเนินการพื้นฐานทั้ง 2 ของ heap จะต้องประกอบด้วยการทำงานบางอย่างที่มันยังคงสถานะความเป็น heap เอาไว้ได้

การบรรจุค่าลงใน heap (Insert, enqueue)

เพื่อบรรจุสมาชิก X เข้าใน heap เราจะสร้างช่องว่าง (hole) ในตำแหน่งว่างที่อยู่ถัดไปจากโนดสุดท้ายของ heap ถ้าสามารถบรรจุ X ลงในช่องว่างนี้ได้โดยไม่ทำให้คุณสมบัติลำดับค่าเสียไป ก็ให้ทำได้เลยและเป็นอันเสร็จสิ้นการทำงาน ไม่เช่นนั้นเราก็จะต้องทำการเลื่อนสมาชิกที่อยู่ในโนดแม่ของช่องว่างลงมาในช่องว่าง ซึ่งก็เป็นการเลื่อนช่องว่างขึ้นไปหาราก และจะทำกระบวนการนี้ซ้ำจนกว่า X จะอยู่ในช่องว่างที่ถูกต้องได้ รูปที่ 6.6 แสดงการบรรจุค่า 14 ลงในทรี เราสร้างช่องว่างให้กับตำแหน่งถัดไปของ heap ถ้าบรรจุ 14 ลงในช่องนี้ก็จะทำให้เสียคุณสมบัติทางลำดับค่าของ heap ดังนั้นจึงเลื่อน 31 ลงในช่องว่างนี้ และเลื่อนช่องว่างขึ้นแทน และทำเช่นนี้ต่อเนื่องขึ้นไปดังรูปที่ 6.7 จนพบตำแหน่งโนดที่ถูกต้อง

วิธีการดังที่กล่าวมานี้เรียกว่า percolate up กล่าวคือสมาชิกตัวใหม่จะไหลขึ้นข้างบนของ heap จนกว่าจะพบกับตำแหน่งที่ถูกต้อง และถ้าสมาชิกตัวใหม่ที่จะบรรจุนั้นเป็นค่าที่น้อยที่สุด มันก็จะถูกเลื่อนให้ขึ้นไปอยู่ที่ตำแหน่งบนสุด รูปที่ 6.8 แสดงฟังก์ชันการบรรจุค่าด้วยกรรมวิธีที่กล่าว เวลาที่ใช้ในการ insert อาจเป็นเวลาที่มากที่สุด คือ O(log N) ได้ ถ้าค่าที่บรรจุนั้นเป็นค่าต่ำสุดและมีการเลื่อนขึ้นจนไปถึงราก อย่างไรก็ตามโดยเฉลี่ยแล้วการเลื่อนขึ้นจะหยุดลงก่อนจะถึงตำแหน่งราก

/* @param x the item to insert. */
public void insert( Comparable x ) throws Overflow
{   if ( isFull( ) )
        throw new Overflow( );
    // Percolate up
    int hole = ++currentSize;
    for( ; hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
} 

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

ฟังก์ชันการลบ deleteMin

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

ถ้า X สามารถใส่ลงในช่องว่างใหม่ที่เกิดขึ้นได้ก็ให้ทำและจบการทำงาน แต่ถ้าไม่ได้เราจะต้องเลื่อนโนดลูกของช่องว่างตัวที่มีค่าน้อยกว่าระหว่างโนดลูกซ้ายและโนดลูกขวาเข้าในช่องว่างซึ่งเป็นการผลักให้ช่องว่างเลื่อนลงข้างล่างหนึ่งระดับ เราจะทำเช่นนี้ไปเรื่อย ๆ จนกว่าจะสามารถใส่ X ลงในช่องว่างได้ นั่นคือการหาตำแหน่งที่ถูกต้องที่จะใส่ X ตามเส้นทางจากโนดรากลงไปนั่นเอง รูปที่ 6.9 ถึงรูปที่ 6.11 แสดงขั้นตอนการทำงาน deleteMin วิธีการทำงานของฟังก์ชันที่ได้กล่าวมานี้เรียกว่า percolate down

ความผิดพลาดที่อาจจะเกิดขึ้นในการใช้งาน heaps คือ เมื่อจำนวนสมาชิกใน heap เป็นเลขคู่ และมีโนดหนึ่งที่มีโนดลูกเพียงโนดเดียว ดังนั้นจึงต้องใช้การทดสอบพิเศษเพิ่มเติมขึ้นมา ในโปรแกรมที่แสดงในรูปที่ 6.12 นั้นเราใช้การทดสอบที่ว่านี้ที่บรรทัดที่ 5 worst-case running time ของการทำงานของฟังก์ชันนี้คือ $O(log\ N)$ โดยเฉลี่ยแล้วสมาชิกที่ถูกใส่ลงที่รากจะถูกเลื่อนลงไปเกือบจะถึงล่างสุดของ heap ดังนั้น average running time จึงเป็น $O(log\ N)$

จากที่กล่าวมาจะเห็นว่า ถึงแม้การค้นหาค่าที่น้อยที่สุดสามารถทำได้ด้วยเวลาคงที่ heap ที่ได้รับการออกแบบสำหรับการค้นหาสมาชิกที่มีค่าน้อยที่สุด (บางที่เรียกว่า Min heap) ก็ไม่ให้ประโยชน์ใด ๆ ถ้าต้องการหาสมาชิกที่มีค่ามากที่สุด ความจริงแล้วเราต้องใช้เวลาเป็น linear time ในการค้นหาค่าใด ๆ ใน heap ทั้งนี้เนื่องจาก heap ไม่มีสารสนเทศการเรียงลำดับค่าอยู่เลยจึงต้องใช้วิธีการ scan ไปทุก ๆ ค่า พิจารณาโครงสร้าง heap ขนาดใหญ่ในรูปที่ 6.13 จะพบว่า ถึงแม้ว่าเราจะรู้ว่าสมาชิกตัวที่มีค่ามากที่สุดอยู่ที่ leaf ตัวใดตัวหนึ่ง ก็ไม่ได้ได้ช่วยให้การทำงานเร็วขึ้น ทั้งนี้เพราะเหตุว่า ครึ่งหนึ่งของจำนวนสมาชิกทั้งหมดยังอยู่ระดับ leaf กรณีที่มีความจำเป็นและสำคัญมากที่จะต้องรู้ตำแหน่งของสมาชิกใน heap ด้วย ก็จำเป็นที่จะต้องใช้โครงสร้างอื่น ๆ เข้าช่วย เช่น ใช้ตารางแฮชร่วมด้วย (อย่าลืมว่าโมเดลของ heap ไม่อนุญาตให้มองเห็นภายใน heap)

public Comparable deleteMin( )
{   if( isEmpty( ) )
        return null;
    Comparable minItem = findMin( );     // return array[1]
    array[ 1 ] = array[ currentSize-- ];
    percolateDown( 1 );
    return minItem;
}
 
private void percolateDown( int hole )
{
/* 1*/  int child;
/* 2*/  Comparable tmp = array[ hole ];
/* 3*/  for( ; hole * 2 <= currentSize; hole = child )
        {
/* 4*/     child = hole * 2;
/* 5*/     if( child != currentSize &&
/* 6*/         array[ child + 1 ].compareTo( array[ child ] ) < 0 )
/* 7*/         child++;
/* 8*/     if( array[ child ].compareTo( tmp ) < 0 )
/* 9*/          array[ hole ] = array[ child ];
           else
/*10*/          break;
        }
/*11*/  array[ hole ] = tmp;
} 

รูปที่ 6.12 ฟังก์ชัน deleteMin ใน binary heap

สมมุติถ้าเรารู้ตำแหน่งของสมาชิกทุกตัว (ด้วยวิธีใดก็ตาม) ก็จะทำให้การดำเนินการอื่น ๆ ทำได้โดยไม่เสียเวลามาก การดำเนินการ 3 อย่างแรกข้างล่างนี้มี worst-case time เป็น logarithmic

decreaseKey
decreaseKey(p, D) ลดค่าของข้อมูลที่ตำแหน่ง p ลงเป็นจำนวน D เนื่องจากการทำงานนี้อาจจะทำให้เสียคุณสมบัติความเป็น heap ดังนั้นจึงต้องจัดการด้วยการทำ percolate up

increaseKey
increaseKey(p, D) เพิ่มค่าของข้อมูลที่ตำแหน่ง p ขึ้นเป็นจำนวน D. เนื่องจากการทำงานนี้อาจจะทำให้เสียคุณสมบัติความเป็น heap ดังนั้นจึงต้องจัดการด้วยการทำ percolate down

delete
delete(p) ลบโนดที่ตำแหน่ง p ออกจาก heap ซึ่งทำได้โดยการทำ decreaseKey(p, $-\infty$) ก่อนจากนั้นตามด้วยการทำ deleteMin()

buildHeap
การดำเนินการ buildHeap ที่มีสมาชิกอินพุต N ตัว เป็นการนำสมาชิก N ตัวมาลงใน heap ว่าง ซึ่งทำโดยการบรรจุค่าเหล่านั้นลงตามลำดับที่อ่านเข้ามา เนื่องจากการบรรจุแต่ละค่าจะใช้เวลาเป็น $O(1)$ โดยเฉลี่ยและใช้เวลาเป็น $O(log\ N)$ สำหรับ worst-case time ดังนั้น running time ทั้งหมดของอัลกอริทึมจึงเป็น $O(N)$ โดยเฉลี่ย แต่เป็น $O(N\ log\ N)$ สำหรับ worst-case เนื่องจากการทำงานนี้จะไม่มีการทำงานอื่น ๆ มาแทรกและเรารู้ว่าเวลาเฉลี่ยที่ใช้ในการทำงานเป็น linear time ดังนั้นเราจึงประกันได้ว่าเวลาการทำงานของมีขอบเขตเป็น linear time

อัลกอริทึมที่ใช้ทั่วไป คือ ใส่ข้อมูล N ตัวลงในทรีโดยไม่ต้องสนใจการเรียงลำดับค่า เพียงแต่รักษาโครงสร้างเท่านั้น จากนั้น ถ้าให้ฟังก์ชัน percolateDown(i) เป็นการเลื่อนลงของโนด i แล้วอัลกอริทึมในรูปที่ 6.14 เป็น pseudocode ที่ใช้ในการสร้างการลำดับค่าตาม heap-order tree

private void buildHeap()
{   for ( int i = currentSize / 2; i > 0; i-- )
	    percolateDown( i );
}

รูปที่ 6.14 เค้าโครงของ buildHeap

รูปทรีด้านซ้ายของรูปที่ 6.15 เป็นทรีที่ไม่ได้มีการจัดเรียกลำดับใด ๆ แต่เกิดจากการบรรจุค่าเรียงตามลำดับที่อ่านค่าเข้ามาเท่านั้น (unordered tree) รูปทรีในรูปที่ 6.15 ถึงรูปที่ 6.18 แสดงผลของการ percolate downs จำนวน 7 รอบ เส้นประของเส้นกิ่งในรูปแสดงให้เห็นถึงการเปรียบเทียบค่า 2 ครั้ง โดยการเปรียบเทียบครั้งแรกเป็นการหาค่าที่น้อยกว่าของโนดลูกอีกครั้งเปรียบเทียบค่าของโนดลูกตัวที่มีค่าน้อยกว่ากับค่าของโนดนั้น ๆ เอง และจากรูปมีจำนวนเส้นประเพียง 10 เส้นเท่านั้น ดังนั้นหมายความว่าจะมีการเทียบค่ากันจำนวน 20 ครั้ง

เพื่อกำหนดขอบเขตเวลาของ running time ของ buildHeap เราจะต้องกำหนดจำนวนเส้นประ เราสามารถทำได้โดยการคำนวณค่าผลรวมของความสูง (sum of the heights) ของโนดทั้งหมดใน heap ซึ่งก็คือจำนวนสูงสุดของเส้นประนั่นเอง และผลบวกทั้งหมดนี้ คือ $O(N)$

ทฤษฎี 6.1 สำหรับ perfect binary tree ที่มีความสูง $h$ ซึ่งมีจำนวนโนดทั้งสิ้น $2^{h+1}–1$ โนด มีผลบวกของความสูงของโนดทั้งหมดเป็น $2^{h+1}–1–(h+1)$

พิสูจน์ จะเห็นได้ว่าทรีจะมีโนดหนึ่งโนดอยู่ที่ระดับความสูง $h$, มี 2 โนดที่ระดับความสูง $= h – 1$, มีโนดจำนวน $2^2$ โนดที่ระดับความสูง $= h – 2$, จึงกล่าวได้ว่าทรีนี้มีโนดจำนวน $2^i$ โนดที่ระดับความสูง $= h – i$ ดังนั้นผลบวกของความสูงของโนดทั้งหมด คือ \begin{align*} S & =∑_{i=0}^h 2^i(h-i) \\ & = h+2(h-1)+4(h-2)+8(h-3)+16(h-4)+⋯+2^{h-1} (1) \ \ \text{(6.1)} \\ \text{คูณด้วย 2 จะได้ } \\ 2S &= 2h+4(h-1)+8(h-2)+16(h-3)+32(h-4)+⋯+2^h (1) \ \ \text{(6.2)} \\ \end{align*} สมการทั้งสองลบกันจะได้สมการที่ 6.3 จะเห็นว่าเทอมเกือบทั้งหมดหักลบกัน เช่น เรามี $2h – 2(h – 1) = 2, 4(h – 1) – 4(h – 2) = 4$ และ ฯลฯ เทอมสุดท้ายของสมการ 6.2 คือ 2h ไม่ปรากฏอยู่ในสมการ 6.1 ดังนั้นมันจึงยังคงเหลืออยู่ในสมการ 6.3 เทอมแรกในสมการ 6.1 คือ h ก็ไม่อยู่ในสมการ 6.2 ดังนั้นจึงมีค่า –h ปรากฏอยู่ในสมการ 6.3 ดังนั้นจะได้ $$S=-h+2+4+8+⋯+2^{h-1}+2^h=(2^{h+1}-1) - (h+1) \ \ \text{(6.3)}$$ ซึ่งเป็นการพิสูจน์ทฤษฎี

ไบนารีทรีที่เป็น complete tree ไม่ได้เป็น perfect tree แต่ผลลัพธ์ที่ได้ข้างบนนี้ก็เป็นขอบเขตบนของผลบวกของความสูงของโนดใน complete tree เนื่องจาก complete tree มีจำนวนโนดอยู่ระหว่าง $2^h$ ถึง $2^{h+1}$ โนด ดังนั้นโดยทฤษฎีนี้จึงถือได้ว่าผลบวกนี้มีค่าเป็น $O(N)$ เมื่อ $N$ คือจำนวนโนด