Dado el recorrido de orden de niveles de un árbol binario completo , determine si el árbol binario es un montón mínimo válido
Ejemplos:
Input : level = [10, 15, 14, 25, 30]
Output : True
The tree of the given level order traversal is
10
/ \
15 14
/ \
25 30
We see that each parent has a value less than
its child, and hence satisfies the min-heap
property
Input : level = [30, 56, 22, 49, 30, 51, 2, 67]
Output : False
The tree of the given level order traversal is
30
/ \
56 22
/ \ / \
49 30 51 2
/
67
We observe that at level 0, 30 > 22, and hence
min-heap property is not satisfied
Necesitamos verificar si cada Node que no es hoja (principal) satisface la propiedad del montón . Para esto, verificamos si cada padre (en el índice i) es más pequeño que sus hijos (en los índices 2*i+1 y 2*i+2, si el padre tiene dos hijos). Si solo hay un hijo, solo verificamos el padre contra el índice 2 * i + 1.
C++
// C++ program to check if a given tree is
// Binary Heap or not
#include <bits/stdc++.h>
using namespace std;
// Returns true if given level order traversal
// is Min Heap.
bool isMinHeap(int level[], int n)
{
// First non leaf node is at index (n/2-1).
// Check whether each parent is greater than child
for (int i=(n/2-1) ; i>=0 ; i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if (level[i] > level[2 * i + 1])
return false;
if (2*i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
// Driver code
int main()
{
int level[] = {10, 15, 14, 25, 30};
int n = sizeof(level)/sizeof(level[0]);
if (isMinHeap(level, n))
cout << "True";
else
cout << "False";
return 0;
}
Java
// Java program to check if a given tree is
// Binary Heap or not
import java.io.*;
import java.util.*;
public class detheap
{
// Returns true if given level order traversal
// is Min Heap.
static boolean isMinHeap(int []level)
{
int n = level.length - 1;
// First non leaf node is at index (n/2-1).
// Check whether each parent is greater than child
for (int i=(n/2-1) ; i>=0 ; i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if (level[i] > level[2 * i + 1])
return false;
if (2*i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args)
throws IOException
{
// Level order traversal
int[] level = new int[]{10, 15, 14, 25, 30};
if (isMinHeap(level))
System.out.println("True");
else
System.out.println("False");
}
}
Python3
# Python3 program to check if a given
# tree is Binary Heap or not
# Returns true if given level order
# traversal is Min Heap.
def isMinHeap(level, n):
# First non leaf node is at index
# (n/2-1). Check whether each parent
# is greater than child
for i in range(int(n / 2) - 1, -1, -1):
# Left child will be at index 2*i+1
# Right child will be at index 2*i+2
if level[i] > level[2 * i + 1]:
return False
if 2 * i + 2 < n:
# If parent is greater than right child
if level[i] > level[2 * i + 2]:
return False
return True
# Driver code
if __name__ == '__main__':
level = [10, 15, 14, 25, 30]
n = len(level)
if isMinHeap(level, n):
print("True")
else:
print("False")
# This code is contributed by PranchalK
C#
// C# program to check if a given tree
// is Binary Heap or not
using System;
class GFG
{
// Returns true if given level
// order traversal is Min Heap.
public static bool isMinHeap(int[] level)
{
int n = level.Length - 1;
// First non leaf node is at
// index (n/2-1). Check whether
// each parent is greater than child
for (int i = (n / 2 - 1) ; i >= 0 ; i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if (level[i] > level[2 * i + 1])
{
return false;
}
if (2 * i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
{
return false;
}
}
}
return true;
}
// Driver code
public static void Main(string[] args)
{
// Level order traversal
int[] level = new int[]{10, 15, 14, 25, 30};
if (isMinHeap(level))
{
Console.WriteLine("True");
}
else
{
Console.WriteLine("False");
}
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to check if a given tree
// is Binary Heap or not
// Returns true if given level order
// traversal is Min Heap.
function isMinHeap($level, $n)
{
// First non leaf node is at index
// (n/2-1). Check whether each parent
// is greater than child
for ($i = ($n / 2 - 1); $i >= 0; $i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if ($level[$i] > $level[2 * $i + 1])
return false;
if (2 * $i + 2 < $n)
{
// If parent is greater than right child
if ($level[$i] > $level[2 * $i + 2])
return false;
}
}
return true;
}
// Driver code
$level = array(10, 15, 14, 25, 30);
$n = sizeof($level);
if (isMinHeap($level, $n))
echo "True";
else
echo "False";
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// JavaScript program to check if a given tree
// is Binary Heap or not
// Returns true if given level
// order traversal is Min Heap.
function isMinHeap(level)
{
var n = level.length - 1;
// First non leaf node is at
// index (n/2-1). Check whether
// each parent is greater than child
for(var i = (n / 2 - 1) ; i >= 0 ; i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if (level[i] > level[2 * i + 1])
{
return false;
}
if (2 * i + 2 < n)
{
// If parent is greater than right child
if (level[i] > level[2 * i + 2])
{
return false;
}
}
}
return true;
}
// Driver code
// Level order traversal
var level = [10, 15, 14, 25, 30];
if (isMinHeap(level))
{
document.write("True");
}
else
{
document.write("False");
}
</script>
Producción:
True
Estos algoritmos se ejecutan con la peor complejidad O(n)
Complejidad espacial: O(1) ya que usa variables constantes
Este artículo es una contribución de Deepak Srivatsav . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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