# 如何检查给定数组是否可表示为二叉堆？

## 本文概述

``````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.``````

## 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 a leaf node
if (i >= (n - 2) / 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 a leaf node
if (i >= (n - 2 ) / 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 a leaf node
if i > = int ((n - 2 ) / 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 a leaf node
if (i >= (n - 2) / 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 a leaf node
if ( \$i >= ( \$n - 2) / 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
?>``````

``Yes``

## 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
?>``````

``Yes``

• 回顶