Imprime todos los Nodes hoja de Binary Heap

Dada una array de N elementos que denota la representación de la array del montón binario , la tarea es encontrar los Nodes hoja de este montón binario .

Ejemplos: 

Input: 
arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 4 5 6 7
Explanation:
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
Leaf nodes of the Binary Heap are:
4 5 6 7
         
Input: 
arr[] = {1, 2, 3, 4, 5,
         6, 7, 8, 9, 10}
Output: 6 7 8 9 10
Explanation:
                1
             /     \
            2       3
          /   \    / \
         4      5 6   7
       /   \   /
      8     9 10
Leaf Nodes of the Binary Heap are:
6 7 8 9 10

Enfoque: La observación clave en el problema es que cada Node hoja del montón binario estará en la altura H o H -1, si H es la altura del montón binario. Por lo tanto, los Nodes hoja se pueden calcular de la siguiente manera:

• Calcule la altura total del montón binario .
• Recorra la array en orden inverso y compare la altura de cada Node con la altura de cálculo H del montón binario.
• Si la altura del Node actual es H, agregue el Node actual a los Nodes hoja.
• De lo contrario, si la altura del Node actual es H-1 y no hay Nodes secundarios, agregue también el Node como Node hoja.

A continuación se muestra la implementación del enfoque anterior:

// Java implementation to print
// the leaf nodes of a Binary Heap
 
import java.lang.*;
import java.util.*;
class GFG {
 
    // Function to calculate height
    // of the Binary heap with given
    // the count of the nodes
    static int height(int N)
    {
        return (int)Math.ceil(
                   Math.log(N + 1)
                   / Math.log(2))
            - 1;
    }
 
    // Function to find the leaf
    // nodes of binary heap
    static void findLeafNodes(
        int arr[], int n)
    {
        // Calculate the height of
        // the complete binary tree
        int h = height(n);
 
        ArrayList<Integer> arrlist
            = new ArrayList<>();
 
        for (int i = n - 1; i >= 0; i--) {
            if (height(i + 1) == h) {
                arrlist.add(arr[i]);
            }
            else if (height(i + 1) == h - 1
                     && n <= ((2 * i) + 1)) {
 
                // if the height if h-1,
                // then there should not
                // be any child nodes
                arrlist.add(arr[i]);
            }
            else {
                break;
            }
        }
        printLeafNodes(arrlist);
    }
 
    // Function to print the leaf nodes
    static void printLeafNodes(
        ArrayList<Integer> arrlist)
    {
        for (int i = arrlist.size() - 1;
             i >= 0; i--) {
            System.out.print(
                arrlist.get(i) + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5,
                      6, 7, 8, 9, 10 };
        findLeafNodes(arr, arr.length);
    }
}

// C# implementation to print
// the leaf nodes of a Binary Heap
using System;
using System.Collections.Generic;
class GFG{
 
// Function to calculate height
// of the Binary heap with given
// the count of the nodes
static int height(int N)
{
    return (int)Math.Ceiling(
                Math.Log(N + 1) /
                Math.Log(2)) - 1;
}
 
// Function to find the leaf
// nodes of binary heap
static void findLeafNodes(int []arr,
                          int n)
{
    // Calculate the height of
    // the complete binary tree
    int h = height(n);
 
    List<int> arrlist = new List<int>();
 
    for (int i = n - 1; i >= 0; i--)
    {
        if (height(i + 1) == h)
        {
            arrlist.Add(arr[i]);
        }
        else if (height(i + 1) == h - 1 &&
                 n <= ((2 * i) + 1))
        {
 
            // if the height if h-1,
            // then there should not
            // be any child nodes
            arrlist.Add(arr[i]);
        }
        else
        {
            break;
        }
    }
    printLeafNodes(arrlist);
}
 
// Function to print the leaf nodes
static void printLeafNodes(List<int> arrlist)
{
    for (int i = arrlist.Count - 1; i >= 0; i--)
    {
        Console.Write(arrlist[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5,
                  6, 7, 8, 9, 10 };
    findLeafNodes(arr, arr.Length);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation to print
# the leaf nodes of a Binary Heap
import math
 
def height(N):
 
    return math.log(N + 1) // math.log(2)
   
# Function to find the leaf
# nodes of binary heap
def findLeafNodes(arr, n):
 
    # Calculate the height of
    # the complete binary tree
    h = height(n)
     
    arrlist = []
   
    for i in range(n - 1,-1,-1):
        if (height(i + 1) == h):
            arrlist.append(arr[i])
        elif (height(i + 1) == h - 1 and n <= ((2 * i) + 1)):
   
            # if the height if h-1,
            # then there should not
            # be any child nodes
            arrlist.append(arr[i])
        else:
            break
 
    prLeafNodes(arrlist)
   
# Function to pr the leaf nodes
def prLeafNodes(arrlist):
 
    for i in range(len(arrlist) - 1,-1,-1):
        print(arrlist[i],end=" ")
   
# Driver Code
arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
findLeafNodes(arr, len(arr))
 
# This code is contributed by shinjanpatra

<script>
// JavaScript implementation to print
// the leaf nodes of a Binary Heap
function height(N){
 
    return Math.floor(Math.log(N + 1) / Math.log(2))
}
   
// Function to find the leaf
// nodes of binary heap
function findLeafNodes(arr, n){
 
    // Calculate the height of
    // the complete binary tree
    let h = height(n)
     
    let arrlist = []
   
    for(let i = n - 1;i >= 0 ;i--){
        if (height(i + 1) == h)
            arrlist.push(arr[i])
        else if (height(i + 1) == h - 1 && n <= ((2 * i) + 1))
   
            // if the height if h-1,
            // then there should not
            // be any child nodes
            arrlist.push(arr[i])
        else
            break
    }
 
    prLeafNodes(arrlist)
}
   
// Function to pr the leaf nodes
function prLeafNodes(arrlist){
 
    for(let i = arrlist.length - 1 ; i>=-0; i--)
        document.write(arrlist[i]," ")
}
   
// Driver Code
 
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
findLeafNodes(arr, arr.length)
 
// This code is contributed by shinjanpatra
 
</script>

6 7 8 9 10

Análisis de rendimiento:

• Complejidad temporal: O(L), donde L es el número de Nodes hoja.
• Espacio Auxiliar: O(1)