Dada una array, cómo verificar si la array dada representa un Binary Max-Heap .
Ejemplos:
Input: arr[] = {90, 15, 10, 7, 12, 2}
Output: True
The given array represents below tree
90
/ \
15 10
/ \ /
7 12 2
The tree follows max-heap property as every
node is greater than all of its descendants.
Input: arr[] = {9, 15, 10, 7, 12, 11}
Output: False
The given array represents below tree
9
/ \
15 10
/ \ /
7 12 11
The tree doesn't follows max-heap property 9 is
smaller than 15 and 10, and 10 is smaller than 11.
Una solución simple es verificar primero si la raíz es mayor que todos sus descendientes. Luego verifique si hay hijos de la raíz. La complejidad temporal de esta solución es O(n 2 )
Una solución eficiente es comparar root solo con sus hijos (no todos los descendientes), si root es mayor que sus hijos y lo mismo es cierto para todos los Nodes, entonces el árbol es max-heap (Esta conclusión se basa en la propiedad transitiva del operador >, es decir, si x > yey y > z, entonces x > z).
El último Node interno está presente en el índice (n-2)/2, suponiendo que la indexación comience con 0.
A continuación se muestra la implementación de esta solución.
C++
// C program to check whether a given array
// represents a max-heap or not
#include <limits.h>
#include <stdio.h>
// Returns true if arr[i..n-1] represents a
// max-heap
bool isHeap(int arr[], int i, int n)
{
// If (2 * i) + 1 >= n, then leaf node, so return true
if (i >= (n - 1) / 2)
return true;
// If an internal node and is
// greater than its children,
// and same is recursively
// true for the children
if (arr[i] >= arr[2 * i + 1] &&
arr[i] >= arr[2 * i + 2]
&& isHeap(arr, 2 * i + 1, n)
&& isHeap(arr, 2 * i + 2, n))
return true;
return false;
}
// Driver program
int main()
{
int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 };
int n = sizeof(arr) / sizeof(int) - 1;
isHeap(arr, 0, n) ? printf("Yes") : printf("No");
return 0;
}
Java
// Java program to check whether a given array
// represents a max-heap or not
class GFG
{
// Returns true if arr[i..n-1]
// represents a max-heap
static boolean isHeap(int arr[],
int i, int n)
{
// If (2 * i) + 1 >= n, then leaf node, so return true
if (i >= (n - 1) / 2)
{
return true;
}
// If an internal node and
// is greater than its
// children, and same is
// recursively true for the
// children
if (arr[i] >= arr[2 * i + 1]
&& arr[i] >= arr[2 * i + 2]
&& isHeap(arr, 2 * i + 1, n)
&& isHeap(arr, 2 * i + 2, n))
{
return true;
}
return false;
}
// Driver program
public static void main(String[] args)
{
int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 };
int n = arr.length - 1;
if (isHeap(arr, 0, n)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
// This code contributed by 29AjayKumar
Python3
# Python3 program to check whether a
# given array represents a max-heap or not
# Returns true if arr[i..n-1]
# represents a max-heap
def isHeap(arr, i, n):
# If (2 * i) + 1 >= n, then leaf node, so return true
if i >= int((n - 1) / 2):
return True
# If an internal node and is greater
# than its children, and same is
# recursively true for the children
if(arr[i] >= arr[2 * i + 1] and
arr[i] >= arr[2 * i + 2] and
isHeap(arr, 2 * i + 1, n) and
isHeap(arr, 2 * i + 2, n)):
return True
return False
# Driver Code
if __name__ == '__main__':
arr = [90, 15, 10, 7, 12, 2, 7, 3]
n = len(arr) - 1
if isHeap(arr, 0, n):
print("Yes")
else:
print("No")
# This code is contributed by PranchalK
C#
// C# program to check whether a given
// array represents a max-heap or not
using System;
class GFG
{
// Returns true if arr[i..n-1] represents a
// max-heap
static bool isHeap(int []arr, int i, int n)
{
// If (2 * i) + 1 >= n, then leaf node, so return true
if (i >= (n - 1) / 2)
{
return true;
}
// If an internal node and is greater
// than its children, and same is
// recursively true for the children
if (arr[i] >= arr[2 * i + 1] &&
arr[i] >= arr[2 * i + 2] &&
isHeap(arr, 2 * i + 1, n) &&
isHeap(arr, 2 * i + 2, n))
{
return true;
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {90, 15, 10, 7, 12, 2, 7, 3};
int n = arr.Length-1;
if (isHeap(arr, 0, n))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
PHP
<?php
// PHP program to check whether a given
// array represents a max-heap or not
// Returns true if arr[i..n-1]
// represents a max-heap
function isHeap($arr, $i, $n)
{
// If (2 * i) + 1 >= n, then leaf node, so return true
if ($i >= ($n - 1) / 2)
return true;
// If an internal node and is greater
// than its children, and same is
// recursively true for the children
if ($arr[$i] >= $arr[2 * $i + 1] &&
$arr[$i] >= $arr[2 * $i + 2] &&
isHeap($arr, 2 * $i + 1, $n) &&
isHeap($arr, 2 * $i + 2, $n))
return true;
return false;
}
// Driver Code
$arr = array(90, 15, 10, 7, 12, 2, 7, 3);
$n = sizeof($arr);
if(isHeap($arr, 0, $n))
echo "Yes";
else
echo "No";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to check whether a given array
// represents a max-heap or not
// Returns true if arr[i..n-1]
// represents a max-heap
function isHeap(arr,i,n)
{
// If (2 * i) + 1 >= n, then leaf node, so return true
if (i >= (n - 1) / 2)
{
return true;
}
// If an internal node and
// is greater than its
// children, and same is
// recursively true for the
// children
if (arr[i] >= arr[2 * i + 1]
&& arr[i] >= arr[2 * i + 2]
&& isHeap(arr, 2 * i + 1, n)
&& isHeap(arr, 2 * i + 2, n))
{
return true;
}
return false;
}
// Driver program
let arr=[ 90, 15, 10, 7, 12, 2, 7, 3 ];
let n = arr.length - 1;
if (isHeap(arr, 0, n)) {
document.write("Yes<br>");
}
else {
document.write("No<br>");
}
// This code is contributed by rag2127
</script>
Producción
Yes
La complejidad temporal de esta solución es O(n). La solución es similar al recorrido de pedido anticipado de Binary Tree.
Gracias a Utkarsh Trivedi por sugerir la solución anterior.
Una solución iterativa es atravesar todos los Nodes internos y verificar que el Node de identificación sea mayor que sus hijos o no.
C++
// C program to check whether a given array
// represents a max-heap or not
#include <stdio.h>
#include <limits.h>
// Returns true if arr[i..n-1] represents a
// max-heap
bool isHeap(int arr[], int n)
{
// Start from root and go till the last internal
// node
for (int i=0; i<=(n-2)/2; i++)
{
// If left child is greater, return false
if (arr[2*i +1] > arr[i])
return false;
// If right child is greater, return false
if (2*i+2 < n && arr[2*i+2] > arr[i])
return false;
}
return true;
}
// Driver program
int main()
{
int arr[] = {90, 15, 10, 7, 12, 2, 7, 3};
int n = sizeof(arr) / sizeof(int);
isHeap(arr, n)? printf("Yes"): printf("No");
return 0;
}
Java
// Java program to check whether a given array
// represents a max-heap or not
class GFG {
// Returns true if arr[i..n-1] represents a
// max-heap
static boolean isHeap(int arr[], int n) {
// Start from root and go till the last internal
// node
for (int i = 0; i <= (n - 2) / 2; i++) {
// If left child is greater, return false
if (arr[2 * i + 1] > arr[i]) {
return false;
}
// If right child is greater, return false
if (2 * i + 2 < n && arr[2 * i + 2] > arr[i]) {
return false;
}
}
return true;
}
// Driver program
public static void main(String[] args) {
int arr[] = {90, 15, 10, 7, 12, 2, 7, 3};
int n = arr.length;
if (isHeap(arr, n)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check whether a
# given array represents a max-heap or not
# Returns true if arr[i..n-1]
# represents a max-heap
def isHeap(arr, n):
# Start from root and go till
# the last internal node
for i in range(int((n - 2) / 2) + 1):
# If left child is greater,
# return false
if arr[2 * i + 1] > arr[i]:
return False
# If right child is greater,
# return false
if (2 * i + 2 < n and
arr[2 * i + 2] > arr[i]):
return False
return True
# Driver Code
if __name__ == '__main__':
arr = [90, 15, 10, 7, 12, 2, 7, 3]
n = len(arr)
if isHeap(arr, n):
print("Yes")
else:
print("No")
# This code is contributed by PranchalK
C#
// C# program to check whether a given array
// represents a max-heap or not
using System;
class GFG
{
// Returns true if arr[i..n-1]
// represents a max-heap
static bool isHeap(int []arr, int n)
{
// Start from root and go till
// the last internal node
for (int i = 0; i <= (n - 2) / 2; i++)
{
// If left child is greater,
// return false
if (arr[2 * i + 1] > arr[i])
{
return false;
}
// If right child is greater,
// return false
if (2 * i + 2 < n && arr[2 * i + 2] > arr[i])
{
return false;
}
}
return true;
}
// Driver Code
public static void Main()
{
int []arr = {90, 15, 10, 7, 12, 2, 7, 3};
int n = arr.Length;
if (isHeap(arr, n))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed
// by 29AjayKumar
PHP
<?php
// PHP program to check whether a
// given array represents a max-heap or not
// Returns true if arr[i..n-1]
// represents a max-heap
function isHeap($arr, $i, $n)
{
// Start from root and go till
// the last internal node
for ($i = 0; $i < (($n - 2) / 2) + 1; $i++)
{
// If left child is greater,
// return false
if($arr[2 * $i + 1] > $arr[$i])
return False;
// If right child is greater,
// return false
if (2 * $i + 2 < $n &&
$arr[2 * $i + 2] > $arr[$i])
return False;
return True;
}
}
// Driver Code
$arr = array(90, 15, 10, 7, 12, 2, 7, 3);
$n = sizeof($arr);
if(isHeap($arr, 0, $n))
echo "Yes";
else
echo "No";
// This code is contributed by Princi Singh
?>
Javascript
<script>
// Javascript program to check
// whether a given array
// represents a max-heap or not
// Returns true if arr[i..n-1]
// represents a max-heap
function isHeap( arr, n)
{
// Start from root and go till
// the last internal node
for (let i=0; i<=Math.floor((n-2)/2); i++)
{
// If left child is greater,
// return false
if (arr[2*i +1] > arr[i])
return false;
// If right child is greater,
// return false
if (2*i+2 < n && arr[2*i+2] > arr[i])
return false;
}
return true;
}
// driver code
let arr = [90, 15, 10, 7, 12, 2, 7, 3];
let n = arr.length;
if (isHeap(arr, n)) {
document.write("Yes");
}
else {
document.write("No");
}
</script>
Producción
Yes
Complejidad de tiempo : O (n) donde n es el número total de elementos en la array dada
Espacio Auxiliar: O(1)
Gracias a Himanshu por sugerir esta solución.
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