Dada la representación de array de min Heap, conviértalo en max Heap en tiempo O(n).
Ejemplo :
Input: arr[] = [3 5 9 6 8 20 10 12 18 9]
3
/ \
5 9
/ \ / \
6 8 20 10
/ \ /
12 18 9
Output: arr[] = [20 18 10 12 9 9 3 5 6 8] OR
[any Max Heap formed from input elements]
20
/ \
18 10
/ \ / \
12 9 9 3
/ \ /
5 6 8
El problema puede parecer complejo a primera vista. Pero nuestro objetivo final es construir solo el montón máximo. La idea es muy simple: simplemente construimos Max Heap sin preocuparnos por la entrada. Comenzamos desde el modo interno más abajo y más a la derecha del montón mínimo y acumulamos todos los modos internos de forma ascendente para construir el montón máximo.
A continuación se muestra su implementación.
C++
// A C++ program to convert min Heap to max Heap
#include<bits/stdc++.h>
using namespace std;
// to heapify a subtree with root at given index
void MaxHeapify(int arr[], int i, int n)
{
int l = 2*i + 1;
int r = 2*i + 2;
int largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
MaxHeapify(arr, largest, n);
}
}
// This function basically builds max heap
void convertMaxHeap(int arr[], int n)
{
// Start from bottommost and rightmost
// internal mode and heapify all internal
// modes in bottom up way
for (int i = (n-2)/2; i >= 0; --i)
MaxHeapify(arr, i, n);
}
// A utility function to print a given array
// of given size
void printArray(int* arr, int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
// Driver program to test above functions
int main()
{
// array representing Min Heap
int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Min Heap array : ");
printArray(arr, n);
convertMaxHeap(arr, n);
printf("\nMax Heap array : ");
printArray(arr, n);
return 0;
}
Java
// Java program to convert min Heap to max Heap
class GFG
{
// To heapify a subtree with root at given index
static void MaxHeapify(int arr[], int i, int n)
{
int l = 2*i + 1;
int r = 2*i + 2;
int largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
// swap arr[i] and arr[largest]
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr, largest, n);
}
}
// This function basically builds max heap
static void convertMaxHeap(int arr[], int n)
{
// Start from bottommost and rightmost
// internal mode and heapify all internal
// modes in bottom up way
for (int i = (n-2)/2; i >= 0; --i)
MaxHeapify(arr, i, n);
}
// A utility function to print a given array
// of given size
static void printArray(int arr[], int size)
{
for (int i = 0; i < size; ++i)
System.out.print(arr[i]+" ");
}
// driver program
public static void main (String[] args)
{
// array representing Min Heap
int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
int n = arr.length;
System.out.print("Min Heap array : ");
printArray(arr, n);
convertMaxHeap(arr, n);
System.out.print("\nMax Heap array : ");
printArray(arr, n);
}
}
// Contributed by Pramod Kumar
Python3
# A Python3 program to convert min Heap
# to max Heap
# to heapify a subtree with root
# at given index
def MaxHeapify(arr, i, n):
l = 2 * i + 1
r = 2 * i + 2
largest = i
if l < n and arr[l] > arr[i]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
MaxHeapify(arr, largest, n)
# This function basically builds max heap
def convertMaxHeap(arr, n):
# Start from bottommost and rightmost
# internal mode and heapify all
# internal modes in bottom up way
for i in range(int((n - 2) / 2), -1, -1):
MaxHeapify(arr, i, n)
# A utility function to print a
# given array of given size
def printArray(arr, size):
for i in range(size):
print(arr[i], end = " ")
print()
# Driver Code
if __name__ == '__main__':
# array representing Min Heap
arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
n = len(arr)
print("Min Heap array : ")
printArray(arr, n)
convertMaxHeap(arr, n)
print("Max Heap array : ")
printArray(arr, n)
# This code is contributed by PranchalK
C#
// C# program to convert
// min Heap to max Heap
using System;
class GFG
{
// To heapify a subtree with
// root at given index
static void MaxHeapify(int []arr,
int i, int n)
{
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
// swap arr[i] and arr[largest]
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr, largest, n);
}
}
// This function basically
// builds max heap
static void convertMaxHeap(int []arr,
int n)
{
// Start from bottommost and
// rightmost internal mode and
// heapify all internal modes
// in bottom up way
for (int i = (n - 2) / 2; i >= 0; --i)
MaxHeapify(arr, i, n);
}
// A utility function to print
// a given array of given size
static void printArray(int []arr,
int size)
{
for (int i = 0; i < size; ++i)
Console.Write(arr[i]+" ");
}
// Driver Code
public static void Main ()
{
// array representing Min Heap
int []arr = {3, 5, 9, 6, 8,
20, 10, 12, 18, 9};
int n = arr.Length;
Console.Write("Min Heap array : ");
printArray(arr, n);
convertMaxHeap(arr, n);
Console.Write("\nMax Heap array : ");
printArray(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program to convert min Heap to max Heap
// utility swap function
function swap(&$a,&$b)
{
$tmp=$a;
$a=$b;
$b=$tmp;
}
// to heapify a subtree with root at given index
function MaxHeapify(&$arr, $i, $n)
{
$l = 2*$i + 1;
$r = 2*$i + 2;
$largest = $i;
if ($l < $n && $arr[$l] > $arr[$i])
$largest = $l;
if ($r < $n && $arr[$r] > $arr[$largest])
$largest = $r;
if ($largest != $i)
{
swap($arr[$i], $arr[$largest]);
MaxHeapify($arr, $largest, $n);
}
}
// This function basically builds max heap
function convertMaxHeap(&$arr, $n)
{
// Start from bottommost and rightmost
// internal mode and heapify all internal
// modes in bottom up way
for ($i = (int)(($n-2)/2); $i >= 0; --$i)
MaxHeapify($arr, $i, $n);
}
// A utility function to print a given array
// of given size
function printArray($arr, $size)
{
for ($i = 0; $i <$size; ++$i)
print($arr[$i]." ");
}
// Driver code
// array representing Min Heap
$arr = array(3, 5, 9, 6, 8, 20, 10, 12, 18, 9);
$n = count($arr);
print("Min Heap array : ");
printArray($arr, $n);
convertMaxHeap($arr, $n);
print("\nMax Heap array : ");
printArray($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to convert min Heap to max Heap
// To heapify a subtree with root at given index
function MaxHeapify(arr , i , n)
{
var l = 2*i + 1;
var r = 2*i + 2;
var largest = i;
if (l < n && arr[l] > arr[i])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
// swap arr[i] and arr[largest]
var temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr, largest, n);
}
}
// This function basically builds max heap
function convertMaxHeap(arr , n)
{
// Start from bottommost and rightmost
// internal mode and heapify all internal
// modes in bottom up way
for (i = (n-2)/2; i >= 0; --i)
MaxHeapify(arr, i, n);
}
// A utility function to print a given array
// of given size
function printArray(arr , size)
{
for (i = 0; i < size; ++i)
document.write(arr[i]+" ");
}
// driver program
// array representing Min Heap
var arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9];
var n = arr.length;
document.write("Min Heap array : ");
printArray(arr, n);
convertMaxHeap(arr, n);
document.write("<br>Max Heap array : ");
printArray(arr, n);
// This code is contributed by 29AjayKumar
</script>
Producción :
Min Heap array : 3 5 9 6 8 20 10 12 18 9 Max Heap array : 20 18 10 12 9 9 3 5 6 8
La complejidad de la solución anterior puede parecer O(nLogn) pero es O(n).
Complejidad espacial: O (n) para la pila de llamadas desde que se usa la recursividad.
Consulte este G-Fact para obtener más detalles.
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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