C++의 최소 힙에서 값 x보다 작은 모든 노드를 인쇄합니다.

이 문제에서는 최소 힙이 제공됩니다. 및 값 x x보다 작은 모든 노드를 인쇄해야 합니다.

최소 힙 모든 노드가 자식 노드의 노드 값보다 작은 값을 갖는 특수한 유형의 이진 트리입니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

X =45

출력 - 2 4 7 10 17 22 33 34

이제 이 문제를 해결하려면 전체 최소 힙에 대한 사전 주문 순회를 수행하고 주어진 값 X보다 작은 값만 인쇄해야 합니다. 노드의 값이 x보다 크면 순회하지 않습니다. 자식 노드의 값은 x보다 큽니다. 최소 힙의 선주문 순회를 수행하기 위해 재귀를 사용할 것입니다.

예

솔루션 작동을 설명하는 프로그램

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

출력

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