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

本文概述

• C++
• Java
• Python3
• C#
• PHP
• C++
• Java
• Python3
• C#
• PHP

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

例子：

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.

一种简单的解决方案：

首先要检查根是否大于其所有后代。然后检查根的子级。该解决方案的时间复杂度为O(n^2)。

一个高效的解决方案是仅将根与其子代(不是所有后代)进行比较, 如果根大于子代且所有节点均相同, 则树为最大堆(此结论基于>运算符的传递属性, 即, 如果x> y和y> z, 则x> z)。

假设索引从0开始, 则最后一个内部节点位于索引(n-2)/ 2。

以下是此解决方案的实现。

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

该解决方案的时间复杂度为O(n)。该解决方案类似于二叉树的遍历遍历。

一个迭代解是遍历所有内部节点并检查id节点是否大于其子节点。

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

感谢Himanshu提出此解决方案。

以上就是检查数组是否可用表示为二叉堆的多个解决方法了。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。