Dado un montón mínimo binario y un valor x, imprima todos los Nodes del montón binario que tengan un valor menor que el valor x dado.
Examples : Consider the below min heap as
common input two both below examples.
2
/ \
3 15
/ \ / \
5 4 45 80
/ \ / \
6 150 77 120
Input : x = 15
Output : 2 3 5 6 4
Input : x = 80
Output : 2 3 5 6 4 77 15 45
La idea es hacer un recorrido de pedido previo del montón binario de dar. Al realizar un recorrido de preorden, si el valor de un Node es mayor que el valor x dado, volvemos a la llamada recursiva anterior. Porque todos los Nodes secundarios en un montón mínimo son mayores que el Node principal. De lo contrario, imprimimos el Node actual y lo recurrimos para sus hijos.
Implementación:
C++
// A C++ program to print all values
// smaller than a given value in Binary
// Heap
#include <bits/stdc++.h>
using namespace std;
// A class for Min Heap
class MinHeap {
// pointer to array of elements in heap
int* harr;
// maximum possible size of min heap
int capacity;
int heap_size; // Current no. of elements.
public:
// Constructor
MinHeap(int capacity);
// to heapify a subtree with root at
// given index
void MinHeapify(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); }
// Inserts a new key 'k'
void insertKey(int k);
// Function to print all nodes smaller than k
void printSmallerThan(int k, int pos);
};
// Function to print all elements smaller than k
void MinHeap::printSmallerThan(int x, int pos = 0)
{
/* Make sure item exists */
if (pos >= heap_size)
return;
if (harr[pos] >= x) {
/* Skip this node and its descendants,
as they are all >= x . */
return;
}
cout << harr[pos] << " ";
printSmallerThan(x, left(pos));
printSmallerThan(x, right(pos));
}
// Constructor: Builds a heap from a given
// array a[] of given size
MinHeap::MinHeap(int cap)
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
// Inserts a new key 'k'
void MinHeap::insertKey(int k)
{
if (heap_size == capacity) {
cout << "\nOverflow: Could not insertKey\n";
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(harr[i], harr[parent(i)]);
i = parent(i);
}
}
// A recursive method to heapify a subtree with
// root at given index. This method assumes that
// the subtrees are already heapified
void MinHeap::MinHeapify(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]);
MinHeapify(smallest);
}
}
// Driver program to test above functions
int main()
{
MinHeap h(50);
h.insertKey(3);
h.insertKey(2);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
h.insertKey(80);
h.insertKey(6);
h.insertKey(150);
h.insertKey(77);
h.insertKey(120);
// Print all nodes smaller than 100.
int x = 100;
h.printSmallerThan(x);
return 0;
}
Java
// A Java program to print all values
// smaller than a given value in Binary
// Heap
// A class for Min Heap
class MinHeap {
// array of elements in heap
int[] harr;
// maximum possible size of min heap
int capacity;
int heap_size; // Current no. of elements.
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
// Function to print all elements smaller than k
void printSmallerThan(int x, int pos)
{
/* Make sure item exists */
if (pos >= heap_size)
return;
if (harr[pos] >= x) {
/* Skip this node and its descendants,
as they are all >= x . */
return;
}
System.out.print(harr[pos] + " ");
printSmallerThan(x, left(pos));
printSmallerThan(x, right(pos));
}
// Constructor: Builds a heap of given size
public MinHeap(int cap)
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
// Inserts a new key 'k'
void insertKey(int k)
{
if (heap_size == capacity) {
System.out.println("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// A utility function to swap two elements
void swap(int x, int y)
{
int temp = harr[x];
harr[x] = harr[y];
harr[y] = temp;
}
// Driver code
public static void main(String[] args)
{
MinHeap h = new MinHeap(15);
h.insertKey(3);
h.insertKey(2);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
h.insertKey(80);
h.insertKey(6);
h.insertKey(150);
h.insertKey(77);
h.insertKey(120);
// Print all nodes smaller than 100.
int x = 100;
h.printSmallerThan(x, 0);
}
};
// This code is contributed by shubham96301
C#
// A C# program to print all values
// smaller than a given value in
// Binary Heap
using System;
// A class for Min Heap
public class MinHeap
{
// array of elements in heap
int[] harr;
// maximum possible size of min heap
int capacity;
// Current no. of elements
int heap_size;
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
// Function to print
// all elements smaller than k
void printSmallerThan(int x, int pos)
{
/* Make sure item exists */
if (pos >= heap_size)
return;
if (harr[pos] >= x)
{
/* Skip this node and its descendants,
as they are all >= x . */
return;
}
Console.Write(harr[pos] + " ");
printSmallerThan(x, left(pos));
printSmallerThan(x, right(pos));
}
// Constructor: Builds a heap of given size
public MinHeap(int cap)
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
// Inserts a new key 'k'
void insertKey(int k)
{
if (heap_size == capacity)
{
Console.WriteLine("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property
// if it is violated
while (i != 0 &&
harr[parent(i)] > harr[i])
{
swap(i, parent(i));
i = parent(i);
}
}
// A utility function to swap two elements
void swap(int x, int y)
{
int temp = harr[x];
harr[x] = harr[y];
harr[y] = temp;
}
// Driver code
public static void Main(String[] args)
{
MinHeap h = new MinHeap(15);
h.insertKey(3);
h.insertKey(2);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
h.insertKey(80);
h.insertKey(6);
h.insertKey(150);
h.insertKey(77);
h.insertKey(120);
// Print all nodes smaller than 100.
int x = 100;
h.printSmallerThan(x, 0);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// A JavaScript program to print all values
// smaller than a given value in Binary
// Heap
// A class for Min Heap
class MinHeap {
// Constructor: Builds a heap of given size
constructor(capacity){
this.harr = new Array(capacity); // array of elements in heap
this.capacity = capacity; // maximum possible size of min heap
this.heap_size = 0; // Current no. of elements.
}
parent(i) { return parseInt((i - 1) / 2); }
left(i) { return (2 * i + 1); }
right(i) { return (2 * i + 2); }
// Function to print all elements smaller than k
printSmallerThan(x, pos)
{
/* Make sure item exists */
if (pos >= this.heap_size)
return;
if (this.harr[pos] >= x) {
/* Skip this node and its descendants,
as they are all >= x . */
return;
}
document.write(this.harr[pos] , " ");
this.printSmallerThan(x, this.left(pos));
this.printSmallerThan(x, this.right(pos));
}
// A utility function to swap two elements
swap(x, y)
{
let temp = this.harr[x];
this.harr[x] = this.harr[y];
this.harr[y] = temp;
}
// Inserts a new key 'k'
insertKey(k)
{
if (this.heap_size == this.capacity) {
System.out.println("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
this.heap_size++;
let i = this.heap_size - 1;
this.harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && this.harr[this.parent(i)] > this.harr[i]) {
this.swap(i, this.parent(i));
i = this.parent(i);
}
}
}
// Driver code
let h = new MinHeap(15);
h.insertKey(3);
h.insertKey(2);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
h.insertKey(80);
h.insertKey(6);
h.insertKey(150);
h.insertKey(77);
h.insertKey(120);
// Print all nodes smaller than 100.
let x = 100;
h.printSmallerThan(x, 0);
// This code is contributed by Shinjan Patra
</script>
Producción
2 3 5 6 4 77 15 45 80
Este artículo es una contribución de Raghav Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA