สร้าง Heap จากอาเรย์ และ Heap Sort

นึกภาพก่อน

ถ้ามีข้อมูลทั้งหมดอยู่ในมือแล้ว จะสร้าง heap อย่างไร วิธีตรง ๆ คือ enqueue ทีละตัว แต่มีวิธีที่เร็วกว่า: มองอาเรย์เป็นต้นไม้ทันที แล้ว "ซ่อม" จากล่างขึ้นบน

เมื่อสร้าง heap ได้ ก็เรียงลำดับข้อมูลได้เลย เพราะ heap ส่งตัวมากสุดออกมาให้ทีละตัว

สร้าง heap: วิธีที่ 1 enqueue ทีละตัว

java

public BinaryHeap(Object[] d) {
  for (int i = 0; i < d.length; i++) enqueue(d[i]);
}

ได้ผลถูกต้อง แต่ enqueue แต่ละครั้งเป็น O(log n) ทำ n ครั้งจึงเป็น O(n log n) สไลด์บอกว่า "เสียเวลามากไป"

สร้าง heap: วิธีที่ 2 ค่อย ๆ ปรับ

java

public BinaryHeap(Object[] d) {
  elementData = (Object[]) d.clone();
  size = d.length;
  for (int i = size - 1; i >= 0; i--) fixDown(i);
}

คัดลอกอาเรย์มาทั้งก้อน มองเป็นต้นไม้ทวิภาคได้ดุลทันที (ลูกซ้ายของ k คือ 2k + 1)
เรียก fixDown(i) กับทุกปม จากปมท้ายสุดย้อนขึ้นมาหาราก

ทำไมต้องจากท้ายมาหน้า: fixDown(i) ใช้ได้ถูกต้องเมื่อต้นไม้ย่อยของลูกทั้งสองเป็น heap อยู่แล้ว การไล่จากท้ายรับประกันว่าลูกถูกซ่อมก่อนพ่อเสมอ

ปมที่เป็นใบไม่มีลูก fixDown จึงจบทันทีโดยไม่ทำอะไร
งานจริงเริ่มที่ปมภายในตัวสุดท้าย

สไลด์เทียบว่าวิธีนี้ใช้เวลา O(n) ขณะที่วิธีแรกเป็น O(n log n)

Heap Sort

รับอาเรย์มาสร้างเป็น max heap
วน dequeue ข้อมูลตัวมากสุด นำไปวาง ณ ตำแหน่งหลังสุดของกลุ่มที่ยังไม่เรียง

java

public static void heapSort(Object[] data) {
  BinaryHeap h = new BinaryHeap(0);
  h.elementData = data;
  h.size = data.length;
  for (int k = h.size - 1; k >= 0; k--) {   // จัดให้อยู่ในรูป binary heap
    h.fixDown(k);
  }
  for (int k = h.size - 1; k > 0; k--) {    // ดึงข้อมูลออกมา (เรียงน้อยไปมาก)
    data[k] = h.dequeue();
  }
}

เคล็ดลับคือ heap ใช้ อาเรย์ตัวเดียวกับข้อมูล (h.elementData = data) เมื่อ dequeue แล้ว size ลดลงหนึ่ง ช่องท้ายของ heap จึงว่างพอดี นำตัวมากสุดที่ได้ไปวางในช่องนั้น ส่วนหน้าของอาเรย์เป็น heap ที่หดลง ส่วนหลังเป็นข้อมูลที่เรียงแล้วซึ่งโตขึ้น

ผลลัพธ์เรียง จากน้อยไปมาก เพราะตัวมากสุดถูกวางไว้ท้ายก่อน

ตัวอย่างไล่ทีละขั้น

เรียง [25, 12, 10, 11, 27]

ช่วงที่ 1: สร้าง heap (fixDown จาก index 4 ลงมา 0)

i	เกิดอะไร	อาเรย์
4, 3, 2	เป็นใบ ไม่ทำอะไร	`[25, 12, 10, 11, 27]`
1	ลูกของ 12 คือ 11 กับ 27 ตัวมากคือ 27 → สลับ	`[25, 27, 10, 11, 12]`
0	ลูกของ 25 คือ 27 กับ 10 ตัวมากคือ 27 → สลับ แล้ว 25 เทียบลูก 11 กับ 12 ไม่ต้องสลับ	`[27, 25, 10, 11, 12]`

ช่วงที่ 2: dequeue แล้ววางท้าย

k	dequeue ได้	heap ที่เหลือ (ส่วนหน้าของอาเรย์)	ส่วนที่เรียงแล้ว (ส่วนหลัง)
4	27	`[25, 12, 10, 11]`	`[27]`
3	25	`[12, 11, 10]`	`[25, 27]`
2	12	`[11, 10]`	`[12, 25, 27]`
1	11	`[10]`	`[11, 12, 25, 27]`

ได้ [10, 11, 12, 25, 27]

ดูการสร้าง heap ทีละขั้นได้ใน simulation ของบทเรียน Binary Heap โดยเลือกตัวอย่าง "สร้าง heap" หรือพิมพ์ build 25 12 10 11 27

เวลาการทำงาน

งาน	เวลา
สร้าง heap ด้วย enqueue ทีละตัว	O(n log n)
สร้าง heap ด้วย fixDown จากท้ายมาหน้า	O(n)
Heap sort ทั้งหมด	O(n log n) (dequeue n − 1 ครั้ง ครั้งละ O(log n))

จุดที่มักพลาด

1. fixDown จากหน้าไปหลัง

ต้องจาก size - 1 ลงมา 0 ถ้าเริ่มจากรากก่อน ลูกยังไม่เป็น heap ผลที่ได้จะไม่ถูก

2. คิดว่า max heap ให้ผลเรียงจากมากไปน้อย

ตัวมากสุดถูกวางไว้ ท้าย อาเรย์ ผลจึงเรียงจากน้อยไปมาก

3. คิดว่าการสร้าง heap ต้องใช้ fixUp

constructor แบบเร็วใช้ fixDown เท่านั้น (fixUp ใช้กับ enqueue)

4. คิดว่าหลังสร้าง heap อาเรย์เรียงแล้ว

[27, 25, 10, 11, 12] เป็น heap แต่ยังไม่เรียง ต้องทำช่วงที่ 2 ต่อ

5. สับสนเวลาของสองวิธีสร้าง

enqueue ทีละตัว O(n log n) · fixDown จากท้าย O(n)

6. ลูปที่สองวนถึง k = 0

ลูปใช้ k > 0 เมื่อเหลือตัวเดียว ตัวนั้นคือตัวน้อยสุดและอยู่ช่อง 0 ถูกที่แล้ว

เสริมทำไมการสร้างแบบล่างขึ้นบนจึงเป็น O(n)

ปมครึ่งหนึ่งของต้นไม้เป็นใบ ไม่ต้องทำอะไรเลย ปมอีกหนึ่งในสี่อยู่เหนือใบหนึ่งระดับ เลื่อนลงได้มากสุด 1 ขั้น ปมอีกหนึ่งในแปดเลื่อนได้มากสุด 2 ขั้น ไปเรื่อย ๆ ปมที่เลื่อนได้ไกล (ใกล้ราก) มีจำนวนน้อย ผลรวมของงานทั้งหมดจึงไม่เกินค่าคงที่คูณ n ส่วนการ enqueue ทีละตัวกลับกัน: ปมจำนวนมากที่อยู่ล่างสุดอาจต้องเลื่อนขึ้นไปถึงราก

Heap sort ไม่ต้องใช้อาเรย์เสริม (เรียงในที่เดิม) ซึ่งเป็นข้อดีเทียบกับวิธีเรียงบางแบบ

ที่มา: QUEUE_7.pdf หน้า 35–44