Dado un montón mínimo , encuentre el elemento máximo presente en el montón.
Ejemplos:
Input : 10
/ \
25 23
/ \ / \
45 30 50 40
Output : 50
Input : 20
/ \
40 28
Output : 40
Enfoque de fuerza bruta:
podemos verificar todos los Nodes en el montón mínimo para obtener el elemento máximo. Tenga en cuenta que este enfoque funciona en cualquier árbol binario y no utiliza ninguna propiedad del montón mínimo. Tiene una complejidad de tiempo y espacio de O(n). Dado que min-heap es un árbol binario completo, generalmente usamos arreglos para almacenarlos, por lo que podemos verificar todos los Nodes simplemente recorriendo el arreglo. Si el montón se almacena usando punteros, entonces podemos usar la recursividad para verificar todos los Nodes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// maximum element in a
// min heap
int findMaximumElement(int heap[], int n)
{
int maximumElement = heap[0];
for (int i = 1; i < n; ++i)
maximumElement = max(maximumElement, heap[i]);
return maximumElement;
}
// Driver code
int main()
{
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
// 63 65 81
int heap[] = { 10, 25, 23, 45, 50, 30, 35, 63, 65, 81 };
cout << findMaximumElement(heap, n);
return 0;
}
Java
// Java implementation of above approach
class GFG {
// Function to find the maximum element
// in a min heap
static int findMaximumElement(int[] heap, int n) {
int maximumElement = heap[0];
for (int i = 1; i < n; ++i) {
maximumElement = Math.max(maximumElement,
heap[i]);
}
return maximumElement;
}
// Driver code
public static void main(String[] args) {
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
int[] heap = {10, 25, 23, 45, 50,
30, 35, 63, 65, 81};
System.out.print(findMaximumElement(heap, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of above approach # Function to find the maximum element # in a min heap def findMaximumElement(heap, n): maximumElement = heap[0]; for i in range(1, n): maximumElement = max(maximumElement, heap[i]); return maximumElement; # Driver code if __name__ == '__main__': # Number of nodes n = 10; # heap represents the following min heap: # 10 # / \ # 25 23 # / \ / \ # 45 50 30 35 # / \ / #63 65 81 heap = [ 10, 25, 23, 45, 50, 30, 35, 63, 65, 81 ]; print(findMaximumElement(heap, n)); # This code is contributed by Princi Singh
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the maximum element
// in a min heap
static int findMaximumElement(int[] heap, int n)
{
int maximumElement = heap[0];
for (int i = 1; i < n; ++i)
maximumElement = Math.Max(maximumElement,
heap[i]);
return maximumElement;
}
// Driver code
public static void Main()
{
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
int[] heap = { 10, 25, 23, 45, 50,
30, 35, 63, 65, 81 };
Console.Write(findMaximumElement(heap, n));
}
}
// This code is contributed by Akanksha Rai
Javascript
<script>
// JavaScript implementation of above approach
// Function to find the maximum element
// in a min heap
function findMaximumElement(heap , n) {
var maximumElement = heap[0];
for (i = 1; i < n; ++i) {
maximumElement = Math.max(maximumElement,
heap[i]);
}
return maximumElement;
}
// Driver code
// Number of nodes
var n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
var heap = [10, 25, 23, 45, 50,
30, 35, 63, 65, 81];
document.write(findMaximumElement(heap, n));
// This code contributed by aashish1995
</script>
Producción:
81
Enfoque eficiente:
la propiedad min heap requiere que el Node principal sea menor que sus Nodes secundarios. Debido a esto, podemos concluir que un Node que no es hoja no puede ser el elemento máximo ya que su Node secundario tiene un valor más alto. Entonces podemos reducir nuestro espacio de búsqueda a solo Nodes de hoja. En un montón mínimo que tiene n elementos, hay Nodes hoja ceil(n/2). La complejidad de tiempo y espacio sigue siendo O (n) como un factor constante de 1/2 que no afecta la complejidad asintótica.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// maximumelement in a
// max heap
int findMaximumElement(int heap[], int n)
{
int maximumElement = heap[n / 2];
for (int i = 1 + n / 2; i < n; ++i)
maximumElement = max(maximumElement, heap[i]);
return maximumElement;
}
// Driver code
int main()
{
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
int heap[] = { 10, 25, 23, 45, 50, 30, 35, 63, 65, 81 };
cout << findMaximumElement(heap, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Function to find the
// maximumelement in a
// max heap
static int findMaximumElement(int heap[], int n)
{
int maximumElement = heap[n / 2];
for (int i = 1 + n / 2; i < n; ++i)
maximumElement = Math.max(maximumElement, heap[i]);
return maximumElement;
}
// Driver code
public static void main(String args[])
{
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
int heap[] = { 10, 25, 23, 45, 50, 30, 35, 63, 65, 81 };
System.out.println(findMaximumElement(heap, n));
}
}
Python 3
# Python 3 implementation of # above approach # Function to find the maximum # element in a max heap def findMaximumElement(heap, n): maximumElement = heap[n // 2] for i in range(1 + n // 2, n): maximumElement = max(maximumElement, heap[i]) return maximumElement # Driver Code n = 10 # Numbers Of Node # heap represents the following min heap: # 10 # / \ # 25 23 # / \ / \ # 45 50 30 35 # / \ / # 63 65 81 heap = [10, 25, 23, 45, 50, 30, 35, 63, 65, 81] print(findMaximumElement(heap, n)) # This code is contributed by Yogesh Joshi
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the
// maximumelement in a
// max heap
static int findMaximumElement(int[] heap,
int n)
{
int maximumElement = heap[n / 2];
for (int i = 1 + n / 2; i < n; ++i)
maximumElement = Math.Max(maximumElement,
heap[i]);
return maximumElement;
}
// Driver code
public static void Main()
{
// Number of nodes
int n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
//63 65 81
int[] heap = { 10, 25, 23, 45, 50,
30, 35, 63, 65, 81 };
Console.WriteLine(findMaximumElement(heap, n));
}
}
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// javascript implementation of above approach
// Function to find the
// maximumelement in a
// max heap
function findMaximumElement(heap , n) {
var maximumElement = heap[n / 2];
for (i = 1 + n / 2; i < n; ++i)
maximumElement = Math.max(maximumElement, heap[i]);
return maximumElement;
}
// Driver code
// Number of nodes
var n = 10;
// heap represents the following min heap:
// 10
// / \
// 25 23
// / \ / \
// 45 50 30 35
// / \ /
// 63 65 81
var heap = [ 10, 25, 23, 45, 50, 30, 35, 63, 65, 81 ];
document.write(findMaximumElement(heap, n));
// This code contributed by aashish1995
</script>
Producción:
81