In Tất Cả Nút Nhỏ Hơn Giá Trị X Trong Min Heap Trong C++

Trong bài toán này, chúng ta được cho một Min Heap và một giá trị x. In tất cả các nút nhỏ hơn x.

Min heap là loại cây nhị phân đặc biệt mà mỗi nút có giá trị nhỏ hơn giá trị nút con của nó.

Ví dụ để hiểu vấn đề:

X = 45

Đầu ra – 2 4 7 10 17 22 33 34

Để giải quyết, ta duyệt preorder toàn bộ min-heap và chỉ in giá trị nhỏ hơn X. Nếu giá trị nút > x thì không duyệt cây con vì giá trị con sẽ lớn hơn. Sử dụng đệ quy cho preorder traversal.

Ví Dụ

Chương trình minh họa giải pháp:

#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);
};

void MinHeap::printSmallerNodes(int x, int pos = 0) {
    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! Size Full\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);
    int r = right(i);
    int 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 << "Tất cả nút có giá trị nhỏ hơn " << x << " là:\n";
    h.printSmallerNodes(x);
    return 0;
}

Đầu Ra

Tất cả nút có giá trị nhỏ hơn 45 là: 2 4 34 17 22 7 33 10