In tất cả các nút nhỏ hơn một giá trị x trong một đống tối thiểu trong C ++

Trong vấn đề này, chúng tôi được đưa ra Min Heap và giá trị x và chúng tôi phải in tất cả các nút nhỏ hơn x.

Khối lượng tối thiểu là một loại cây nhị phân đặc biệt, trong đó mọi nút có giá trị nhỏ hơn giá trị nút của nút con của nó.

Hãy lấy một ví dụ để hiểu vấn đề -

X =45

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

Bây giờ, để giải quyết vấn đề này, chúng ta cần thực hiện theo thứ tự trước của toàn bộ min-heap và chỉ in những giá trị nhỏ hơn giá trị đã cho X. Nếu giá trị của một nút lớn hơn x thì chúng ta sẽ không duyệt. nút con ở đó giá trị sẽ lớn hơn x. Chúng tôi sẽ sử dụng đệ quy để thực hiện đặt hàng trước của min-heap.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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<<"All nodes with value smaller than "<<x<<" are\n";
   h.printSmallerNodes(x);
   return 0;
}

Đầu ra

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