ในปัญหานี้ เราได้รับ Min Heap และค่า x และเราต้องพิมพ์โหนดทั้งหมดที่น้อยกว่า x
ฮีปขั้นต่ำ เป็นไบนารีทรีชนิดพิเศษที่ทุกโหนดมีค่าน้อยกว่าค่าโหนดของโหนดย่อย
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
X =45
ผลลัพธ์ − 2 4 7 10 17 22 33 34
ตอนนี้ เพื่อแก้ปัญหานี้ เราต้องทำการสั่งซื้อล่วงหน้าผ่าน min-heap ทั้งหมด และพิมพ์เฉพาะค่าที่น้อยกว่าค่า X ที่กำหนด หากค่าของโหนดมากกว่า x เราจะไม่ข้ามผ่าน โหนดย่อยมีค่าจะมากกว่า x เราจะใช้การเรียกซ้ำสำหรับการสั่งจองล่วงหน้าของ min-heap
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
