พิมพ์โหนดที่น้อยกว่า X ใน Min Heap ใน C++

ภาพรวมปัญหา

ได้รับ Min Heap และค่า X ต้องพิมพ์โหนดที่มีค่าน้อยกว่า X ทั้งหมด

Min Heap คืออะไร?

Binary Tree ที่โหนดแม่มีค่าน้อยกว่าลูกเสมอ

ตัวอย่าง

X = 45

Output: 2 4 7 10 17 22 33 34

วิธีแก้ปัญหา (Preorder Traversal + Pruning)

1. Preorder Traversal ทั้ง Heap
2. ถ้าโหนด ≥ X → หยุดไม่ไปลึกกว่า (เพราะลูกจะ ≥ โหนดแม่)
3. Time Complexity: O(k) โดย k = จำนวนโหนด < X

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

class MinHeap {
    int* harr;
    int capacity;
    int heap_size;
public:
    MinHeap(int capacity);
    void Heapify(int);
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    void insert(int k);
    void printSmallerNodes(int k, int pos = 0);
};

void MinHeap::printSmallerNodes(int x, int pos) {
    if (pos >= heap_size) return;
    if (harr[pos] >= x) return;
    cout << harr[pos] << " ";
    printSmallerNodes(x, left(pos));
    printSmallerNodes(x, right(pos));
}

MinHeap::MinHeap(int cap) {
    heap_size = 0;
    capacity = cap;
    harr = new int[cap];
}

void MinHeap::insert(int k) {
    if (heap_size == capacity) { cout << "\nOverflow!\n"; return; }
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}

void MinHeap::Heapify(int i) {
    int l = left(i), r = right(i), smallest = i;
    if (l < heap_size && harr[l] < harr[i]) smallest = l;
    if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        Heapify(smallest);
    }
}

int main() {
    MinHeap h(50);
    h.insert(2); h.insert(4); h.insert(7); h.insert(34);
    h.insert(52); h.insert(33); h.insert(10); h.insert(51);
    h.insert(75); h.insert(17); h.insert(22);
    int x = 45;
    cout << "All nodes with value smaller than " << x << " are:\n";
    h.printSmallerNodes(x);
    return 0;
}

ผลลัพธ์ (Output)

All nodes with a value smaller than 45 are:
2 4 34 17 22 7 33 10