26.5 binary heap

หน้า 20.5 ใช้ priority_queue หยิบค่ามากสุดออกมาได้ทุกเมื่อ และบอกว่าข้างในคือ heap ที่เก็บอยู่ใน vector ธรรมดาโดยไม่มี pointer เลย หน้านี้เขียน heap เองทีละขั้น ใส่ หยิบออก สร้าง heap จากอาเรย์ทั้งก้อนใน O(N) และเรียงข้อมูลด้วย heap sort แล้ววัดเทียบกับ priority_queue และ sort รู้ข้างในแล้ว จะใช้ priority_queue ได้มั่นใจขึ้น และเขียนเองได้ในโจทย์ที่ต้องดูหรือแก้ของข้างในซึ่ง priority_queue ไม่ยอมให้ทำ

ต้นไม้ที่เก็บในอาเรย์

binary heap คือ binary tree ที่มีสองกฎ

1. รูปร่าง ทุกชั้นเต็มยกเว้นชั้นล่างสุด และชั้นล่างสุดเติมจากซ้ายไปขวาไม่เว้นช่อง ต้นไม้แบบนี้เรียกว่า complete binary tree
2. ลำดับ ทุกโหนดมีค่ามากกว่าหรือเท่ากับลูกของมัน ค่ามากสุดจึงอยู่ที่รากเสมอ เรียกว่า max-heap ถ้ากลับเป็นน้อยกว่าหรือเท่ากับ จะได้ min-heap แบบ priority_queue ที่ใช้ greater

กฎข้อ 2 อ่อนกว่ากฎของ BST มาก บอกแค่ว่าพ่อไม่น้อยกว่าลูก ไม่ได้บอกว่าลูกซ้ายกับลูกขวาใครมากกว่า heap จึงค้นหาค่าใดๆ ไม่ได้เร็ว แต่บอกค่ามากสุดได้ทันที และกฎข้อ 1 ทำให้เก็บในอาเรย์ได้พอดี ไล่โหนดทีละชั้นจากซ้ายไปขวาใส่ช่อง 1 2 3 ไปเรื่อยๆ โดยไม่ใช้ช่อง 0

เมื่อเริ่มที่ช่อง 1 ทุกโหนดหาพ่อและลูกได้ด้วยเลขคณิตล้วนๆ ไม่ต้องเก็บ pointer เลย

ช่องที่ 2 * i เกินจำนวนของในฮีปแปลว่าไม่มีลูก heap N ตัวสูง log₂ N ปัดลงเสมอเพราะทุกชั้นเต็ม ล้านตัวสูงแค่ 19 ต่างจาก BST ที่ความสูงขึ้นกับลำดับที่ใส่ heap เอียงไม่ได้เลย เพราะกฎรูปร่างบังคับไว้

ใส่และหยิบออก

ใส่ ค่าใหม่ไปต่อท้ายอาเรย์ ซึ่งคือช่องว่างซ้ายสุดของชั้นล่าง กฎรูปร่างยังถูก แต่ค่าใหม่อาจมากกว่าพ่อ ให้สลับกับพ่อไปเรื่อยๆ จนพ่อไม่น้อยกว่ามัน หรือมันขึ้นไปถึงราก เรียกว่า sift up (ลอยขึ้น)

หยิบออก ค่ามากสุดอยู่ที่ช่อง 1 แต่ถ้าลบช่อง 1 ทิ้งต้นไม้จะขาดราก วิธีที่รักษากฎรูปร่างไว้คือเอาตัวท้ายสุดของอาเรย์มาวางที่ช่อง 1 แทน แล้วลดขนาดลงหนึ่ง ตัวที่ขึ้นมาเป็นรากมักเล็กเกินไป ให้สลับกับลูกตัวที่มากกว่าไปเรื่อยๆ จนไม่น้อยกว่าลูกทั้งสอง หรือลงไปถึงใบ เรียกว่า sift down (จมลง) ต้องเป็นลูกตัวที่มากกว่า เพราะมันจะขึ้นมาเป็นพ่อของลูกอีกตัว

#include <bits/stdc++.h>
using namespace std;

vector<int> heap = {0}; // (1)!

void sift_up(int i)
{
    while (i > 1 && heap[i / 2] < heap[i]) { // (2)!
        swap(heap[i / 2], heap[i]);
        i /= 2;
    }
}

void sift_down(int i)
{
    int n = (int)heap.size() - 1;
    while (2 * i <= n) {
        int child = 2 * i;
        if (child + 1 <= n && heap[child + 1] > heap[child]) { // (3)!
            child++;
        }
        if (heap[i] >= heap[child]) { // (4)!
            break;
        }
        swap(heap[i], heap[child]);
        i = child;
    }
}

void push(int x)
{
    heap.push_back(x);
    sift_up((int)heap.size() - 1);
}

int pop()
{
    int top = heap[1];
    heap[1] = heap.back(); // (5)!
    heap.pop_back();
    if (heap.size() > 1) {
        sift_down(1);
    }
    return top;
}

void show()
{
    cout << "heap:";
    for (int i = 1; i < (int)heap.size(); i++) {
        cout << ' ' << heap[i];
    }
    cout << '\n';
}

int main()
{
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        char op;
        cin >> op;
        if (op == '+') {
            int x;
            cin >> x;
            push(x);
            cout << "push " << x << '\n';
        } else {
            cout << "pop " << pop() << '\n';
        }
        show();
    }
    return 0;
}

1. ใส่ 0 ไว้ที่ช่อง 0 ก่อน ของจริงเริ่มที่ช่อง 1 จำนวนของในฮีปจึงเป็น heap.size() - 1
2. ตราบใดที่ยังไม่ใช่รากและพ่อน้อยกว่า สลับแล้วขึ้นไปหนึ่งชั้น
3. เริ่มที่ลูกซ้าย ถ้ามีลูกขวาและลูกขวามากกว่า เปลี่ยนไปใช้ลูกขวา
4. ไม่น้อยกว่าลูกที่มากที่สุดแล้ว กฎลำดับถูกทั้งต้น หยุดได้
5. เอาตัวท้ายมาแทนราก แล้วตัดช่องท้ายทิ้ง ถ้าฮีปเหลือตัวเดียว ตัวท้ายก็คือรากเอง พอ pop_back ฮีปจะว่าง จึงต้องตรวจขนาดก่อนเรียก sift_down โปรแกรมนี้ไม่ได้ตรวจว่าฮีปว่างก่อนหยิบ ข้อมูลเข้าต้องไม่สั่งหยิบตอนว่าง

8
+ 40
+ 70
+ 20
+ 90
+ 60
-
+ 80
-

push 40
heap: 40
push 70
heap: 70 40
push 20
heap: 70 40 20
push 90
heap: 90 70 20 40
push 60
heap: 90 70 20 40 60
pop 90
heap: 70 60 20 40
push 80
heap: 80 70 20 40 60
pop 80
heap: 70 60 20 40

ไล่ตามทีละบรรทัด

• ใส่ 70 ต่อท้ายที่ช่อง 2 พ่อคือ 40 น้อยกว่า จึงสลับ 70 ขึ้นเป็นราก
• ใส่ 90 ที่ช่อง 4 พ่อคือช่อง 2 ซึ่งเป็น 40 สลับขึ้นมา แล้วพ่อตัวใหม่คือ 70 ที่ช่อง 1 สลับอีกครั้ง 90 จึงขึ้นเป็นราก ได้ภาพข้างบนหลังใส่ 60
• หยิบ 90 ออก เอา 60 ที่อยู่ท้ายมาไว้ที่ราก ลูกคือ 70 กับ 20 สลับกับ 70 ที่มากกว่า แล้วลูกตัวเดียวที่เหลือคือ 40 ไม่มากกว่า 60 จึงหยุด

ทั้ง sift up และ sift down เดินไม่เกินความสูงของต้นไม้ ใส่และหยิบออกจึงเป็น O(log N) ดูค่ามากสุดคือดูช่อง 1 เป็น O(1) ตรงกับตารางเวลาของ priority_queue ในหน้า 20.5 ทุกบรรทัด เพราะเป็นสิ่งเดียวกัน

เทียบกับการไล่หาค่ามากสุด

วิธีตรงไปตรงมาคือเก็บค่าไว้ใน vector เฉยๆ ใส่คือ push_back ซึ่งเป็น O(1) หยิบค่ามากสุดคือไล่หาทั้ง vector ซึ่งเป็น O(N) วัดบนเครื่องเดียวกับหน้า 19.1 แบบ -O2 ค่าสุ่มเข้ามา N ตัว ทุกครั้งที่เข้ามาครบสองตัวหยิบค่ามากสุดออกหนึ่งตัว พอเข้าครบแล้วหยิบที่เหลือออกจนหมด รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

วิธีไล่หาช้าลงสี่เท่าเมื่อ N เพิ่มสองเท่า ตามรูปของ O(N²) ล้านตัวคงใช้เป็นนาที ส่วน heap เป็น O(N log N)

สร้าง heap จากอาเรย์ทั้งก้อนใน O(N)

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

#include <bits/stdc++.h>
using namespace std;

void sift_down(vector<int> &a, int i, int n)
{
    while (2 * i <= n) {
        int child = 2 * i;
        if (child + 1 <= n && a[child + 1] > a[child]) {
            child++;
        }
        if (a[i] >= a[child]) {
            break;
        }
        swap(a[i], a[child]);
        i = child;
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = n / 2; i >= 1; i--) { // (1)!
        sift_down(a, i, n);
        cout << "after " << i << ':';
        for (int j = 1; j <= n; j++) {
            cout << ' ' << a[j];
        }
        cout << '\n';
    }
    return 0;
}

1. ช่องที่มากกว่า N / 2 ไม่มีลูก เพราะลูกซ้ายของมันอยู่ที่ช่องเกิน N จึงข้ามใบทั้งหมดไปเลย

8
30 50 10 80 20 70 60 40

after 4: 30 50 10 80 20 70 60 40
after 3: 30 50 70 80 20 10 60 40
after 2: 30 80 70 50 20 10 60 40
after 1: 80 50 70 40 20 10 60 30

ช่อง 4 คือ 80 มากกว่าลูกตัวเดียวคือ 40 อยู่แล้ว ไม่เปลี่ยน ช่อง 3 คือ 10 สลับกับ 70 ช่อง 2 คือ 50 สลับกับ 80 สุดท้ายช่อง 1 คือ 30 จมลงสามชั้น สลับกับ 80 แล้วกับ 50 แล้วกับ 40 จนไปอยู่ช่อง 8 ซึ่งเป็นใบ

ทำไมเป็น O(N) โหนดครึ่งหนึ่งเป็นใบซึ่งไม่ต้องทำอะไร โหนดอีกหนึ่งในสี่อยู่เหนือใบหนึ่งชั้น จมได้ไม่เกิน 1 ชั้น หนึ่งในแปดจมได้ไม่เกิน 2 ชั้น ไล่ไปเรื่อยๆ รวมแล้ว N/4 × 1 + N/8 × 2 + N/16 × 3 + ... ซึ่งไม่เกิน N โหนดที่จมได้ลึกมีน้อย โหนดที่มีเยอะจมได้ตื้น ต่างจากการใส่ทีละตัวที่ตัวท้ายๆ ซึ่งมีเยอะที่สุดอาจต้องลอยขึ้นไปถึงราก วัดบนเครื่องเดียวกัน -O2 นับจำนวนครั้งที่สลับด้วย รันแบบละ 5 รอบ เวลาเป็นค่ากลาง

ข้อมูลเรียงจากน้อยไปมากเป็นกรณีแย่ที่สุดของการใส่ทีละตัว เพราะทุกตัวใหม่มากกว่าทุกตัวที่มีจึงลอยขึ้นถึงราก จำนวนครั้งที่สลับเป็นราว N log₂ N ส่วนวิธี sift down สลับไม่เกิน N ครั้งตามที่คิดไว้ แม้แต่กรณีแย่ที่สุด ข้อมูลสุ่มทั้งสองวิธีใกล้กัน เพราะค่าที่ใส่ทีละตัวส่วนใหญ่ลอยขึ้นไม่กี่ชั้น

heap sort

สร้าง max-heap แล้วหยิบค่ามากสุดออก N - 1 ครั้งก็ได้ค่าเรียงจากมากไปน้อย ทำในอาเรย์เดิมได้เลยโดยไม่ต้องมีอาเรย์ที่สอง ทุกครั้งที่หยิบ สลับรากกับตัวท้ายของฮีป ค่ามากสุดจะไปอยู่ท้ายสุด ซึ่งเป็นตำแหน่งที่มันควรอยู่ในอาเรย์ที่เรียงแล้ว แล้วถือว่าฮีปสั้นลงหนึ่งช่อง ส่วนท้ายอาเรย์ค่อยๆ กลายเป็นส่วนที่เรียงแล้ว

#include <bits/stdc++.h>
using namespace std;

void sift_down(vector<int> &a, int i, int n)
{
    while (2 * i <= n) {
        int child = 2 * i;
        if (child + 1 <= n && a[child + 1] > a[child]) {
            child++;
        }
        if (a[i] >= a[child]) {
            break;
        }
        swap(a[i], a[child]);
        i = child;
    }
}

void heap_sort(vector<int> &a, int n)
{
    for (int i = n / 2; i >= 1; i--) {
        sift_down(a, i, n);
    }
    for (int last = n; last >= 2; last--) {
        swap(a[1], a[last]); // (1)!
        sift_down(a, 1, last - 1); // (2)!
        cout << "heap:";
        for (int j = 1; j < last; j++) {
            cout << ' ' << a[j];
        }
        cout << " | sorted:";
        for (int j = last; j <= n; j++) {
            cout << ' ' << a[j];
        }
        cout << '\n';
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    heap_sort(a, n);
    return 0;
}

1. ค่ามากสุดของฮีปไปอยู่ช่อง last ซึ่งเป็นช่องสุดท้ายที่ยังไม่เรียง
2. ฮีปตอนนี้คือช่อง 1 ถึง last - 1 ตัวที่เพิ่งมาอยู่ที่รากจมลงในฮีปที่สั้นลง ส่วนช่อง last ไม่ถูกแตะอีก

8
30 50 10 80 20 70 60 40

heap: 70 50 60 40 20 10 30 | sorted: 80
heap: 60 50 30 40 20 10 | sorted: 70 80
heap: 50 40 30 10 20 | sorted: 60 70 80
heap: 40 20 30 10 | sorted: 50 60 70 80
heap: 30 20 10 | sorted: 40 50 60 70 80
heap: 20 10 | sorted: 30 40 50 60 70 80
heap: 10 | sorted: 20 30 40 50 60 70 80

สร้างฮีปเป็น O(N) หยิบออก N - 1 ครั้งครั้งละ O(log N) รวมเป็น O(N log N) ทุกกรณี ไม่มีข้อมูลแบบไหนทำให้ช้าลง และไม่ต้องใช้อาเรย์เพิ่ม วัดเทียบกับ sort และการใส่ทุกตัวลง priority_queue แบบน้อยสุดก่อนแล้วหยิบออกจนหมด บนเครื่องเดียวกัน -O2 ค่าสุ่ม 5 รอบ ค่ากลาง

heap sort กับ priority_queue ใช้เวลาระดับเดียวกัน เพราะทำงานแบบเดียวกัน ส่วน sort เร็วกว่าสองถึงสามเท่า ถ้าแค่อยากเรียงข้อมูล ใช้ sort เหมือนเดิม heap sort มีค่าตรงที่เป็นตัวอย่างที่ชัดที่สุดของการใช้ heap และเป็นวิธีเรียง O(N log N) ที่เขียนเองได้สั้นที่สุดวิธีหนึ่ง ส่วน merge sort กับ quick sort อยู่ในบทที่ 22

เขียนเองหรือใช้ priority_queue

ปกติให้ใช้ priority_queue เขียนสั้นกว่าและผิดยากกว่า heap ที่เขียนเองมีประโยชน์เมื่อต้องการสิ่งที่ priority_queue ไม่ยอมให้ทำ

• ดูของข้างใน เช่น โจทย์ถามว่าหลังทำคำสั่งชุดหนึ่งแล้วอาเรย์ของ heap หน้าตาเป็นอย่างไร ซึ่งเป็นแบบฝึกหัดข้อ 6
• สร้างจากข้อมูลทั้งก้อนใน O(N) priority_queue ก็ทำได้ถ้าส่งช่วงของ vector ให้ตอนประกาศ เช่น priority_queue<int> pq(v.begin(), v.end()); แต่ต้องรู้ว่ามีวิธีนี้
• แก้ค่าของตัวที่อยู่ตรงกลางแล้วให้มันลอยขึ้นหรือจมลง ซึ่งต้องรู้ว่าแต่ละค่าอยู่ช่องไหน priority_queue ไม่บอกตำแหน่ง

ใน <algorithm> ยังมี make_heap push_heap pop_heap และ sort_heap ที่ทำงานเดียวกับหน้านี้บน vector ที่เริ่มจากช่อง 0 สูตรลูกและพ่อจึงต่างจากหน้านี้ไปหนึ่ง ดูในส่วนลองทำให้พัง

ลองทำให้พัง

แบบที่ 1 จมลงทางลูกซ้ายเสมอ

ในโปรแกรม heap ลบสามบรรทัดที่เลือกลูกขวาเมื่อลูกขวามากกว่า ให้ sift_down เทียบกับลูกซ้ายอย่างเดียว ข้อมูลเข้าชุดแรกยังได้ผลถูกทุกบรรทัด เพราะบังเอิญลูกซ้ายมากกว่าทุกครั้ง ลองชุดนี้

10
+ 30
+ 10
+ 50
+ 20
-
-
-
+ 40
-
-

push 30
heap: 30
push 10
heap: 30 10
push 50
heap: 50 10 30
push 20
heap: 50 20 30 10
pop 50
heap: 20 10 30
pop 20
heap: 30 10
pop 30
heap: 10
push 40
heap: 40 10
pop 40
heap: 10
pop 10
heap:

หยิบได้ 50 แล้ว 20 แล้ว 30 ทั้งที่ 30 มากกว่า 20 หลังหยิบ 50 ตัวท้ายคือ 10 ขึ้นมาเป็นราก ลูกคือ 20 กับ 30 โปรแกรมดูแค่ลูกซ้าย สลับ 10 กับ 20 แล้วหยุด 20 ขึ้นเป็นรากทั้งที่ลูกขวาของมันคือ 30 กฎลำดับเสียไปแล้วแต่ไม่มีอะไรเตือน บั๊กแบบนี้ผ่านชุดทดสอบเล็กๆ ได้ง่าย ทดสอบ heap ทุกครั้งด้วยการหยิบออกจนหมดแล้วดูว่าได้ค่าเรียงจริงไหม

แบบที่ 2 เริ่มที่ช่อง 0 แต่ใช้สูตรของช่อง 1

ในโปรแกรม heap ตัดเลข 0 ที่ใส่ไว้ช่อง 0 ออกให้เป็น vector<int> heap; เปลี่ยน heap[1] กับ sift_down(1) เป็นช่อง 0 เปลี่ยน i > 1 ใน sift_up เป็น i > 0 ให้ show เริ่มพิมพ์จากช่อง 0 และให้ pop เรียก sift_down เมื่อ heap ยังไม่ว่าง แต่สูตรลูก 2 * i กับ 2 * i + 1 และพ่อ i / 2 ยังเป็นของช่อง 1 ป้อนข้อมูลเข้าชุดแรกได้ผลถูกทุกบรรทัดที่หยิบ ลองชุดนี้

9
+ 10
+ 40
+ 50
+ 60
+ 20
+ 30
+ 70
-
-

push 10
heap: 10
push 40
heap: 40 10
push 50
heap: 50 40 10
push 60
heap: 60 50 10 40
push 20
heap: 60 50 20 40 10
push 30
heap: 60 50 30 40 10 20
push 70
heap: 70 60 30 50 10 20 40
pop 70
heap: 60 50 30 40 10 20
pop 60
heap: 50 40 30 20 10

หยิบได้ 70 แล้ว 60 ถูกอีก ลองสุ่มสั่งใส่และหยิบอีก 300 ชุดเทียบกับ priority_queue ก็ได้ค่าที่หยิบตรงกันทุกชุด เหตุผลคือที่ช่อง 0 สูตรลูกซ้ายได้ช่อง 0 ซึ่งก็คือตัวมันเอง ลูกขวาได้ช่อง 1 และพ่อของช่อง 1 ก็ได้ 1 / 2 = 0 ช่อง 0 จึงกลายเป็นรากที่มีลูกคนเดียวคือช่อง 1 ใต้ช่อง 1 ลงไปเป็น heap แบบเริ่มช่อง 1 เหมือนเดิม ต้นไม้สูงขึ้นหนึ่งชั้นแต่พ่อยังไม่น้อยกว่าลูกทุกคู่ บั๊กนี้จึงเงียบ ปัญหาจะโผล่เมื่อเอา vector นี้ไปใช้กับของที่คิดแบบช่อง 0 จริง เช่น pop_heap หรือ is_heap ใน <algorithm> ซึ่งถือว่าลูกของช่อง 2 คือช่อง 5 กับ 6 บรรทัด heap: 70 60 30 50 10 20 40 ข้างบน ช่อง 2 เป็น 30 แต่ช่อง 6 เป็น 40 เรียก is_heap กับ vector นี้ได้ 0 คือไม่ใช่ heap ถ้าเริ่มที่ช่อง 0 สูตรต้องเป็น ลูกซ้าย 2 * i + 1 ลูกขวา 2 * i + 2 และพ่อ (i - 1) / 2 ให้เลือกแบบใดแบบหนึ่งแล้วใช้ทั้งโปรแกรม เอกสารนี้ใช้ช่อง 1 เพราะสูตรสั้นกว่า

สรุป

• max-heap คือ complete binary tree ที่พ่อไม่น้อยกว่าลูก เก็บในอาเรย์เริ่มช่อง 1 ลูกอยู่ช่อง 2i กับ 2i + 1 พ่ออยู่ช่อง i / 2
• ใส่คือต่อท้ายแล้ว sift up หยิบออกคือเอาตัวท้ายมาแทนรากแล้ว sift down กับลูกตัวที่มากกว่า ทั้งสองเป็น O(log N)
• สร้าง heap จากอาเรย์ทั้งก้อนด้วย sift down จากช่อง N / 2 ลงมาถึงช่อง 1 ใช้ O(N) สลับไม่เกิน N ครั้ง
• heap sort สร้างฮีปแล้วสลับรากไปไว้ท้ายซ้ำๆ เป็น O(N log N) ทุกกรณี แต่ sort เร็วกว่าในทางปฏิบัติ
• priority_queue คือ heap แบบนี้ ใช้มันเป็นหลัก เขียนเองเมื่อต้องดูหรือแก้ของข้างใน