CONVERTIRE IL MUCCHIO DI MIN IN UN MUCCHIO MASSIMO

Dato una rappresentazione di array di MIN HEAP convertilo in heap massimo.

Esempi:

Ingresso: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ / /
12 18 9
stringa.format stringa java
Produzione: arr [] = {20 18 10 12 9 9 3 5 6 8}

20
/
18 10
//
12 9 3
/ / /
5 6 8
Ingresso: arr [] = {3 4 8 11 13}
Produzione: arr [] = {13 11 8 4 3}

L'idea è semplicemente costruire un heap massimo senza prendersi cura dell'input. Inizia dal nodo interno più basso e più a destra di Min-heap e accumula tutti i nodi interni nel modo in basso per costruire il mucchio massimo.

Seguire i passaggi indicati per risolvere il problema:

comandi sql ddl

Chiama la funzione heapify dal nodo interno più a destra di Min-heap
Accumulare tutti i nodi interni in modo bottom-up per costruire un heap massimo
Stampa il massimo

Algoritmo: Ecco un Algoritmo per convertire un mucchio di min in un mucchio massimo :

Inizia dall'ultimo nodo non foglie del heap (cioè il genitore dell'ultimo nodo foglia). Per un mucchio binario questo nodo si trova sul pavimento dell'indice ((n - 1)/2) dove n è il numero di nodi nel mucchio.
Per ogni nodo non focente eseguire un file 'heapify' operazione per correggere la proprietà heap. In un mucchio di min, questa operazione prevede di verificare se il valore del nodo è maggiore di quello dei suoi figli e, se così, scambiare il nodo con il più piccolo dei suoi figli. In un mucchio massimo, l'operazione prevede di verificare se il valore del nodo è inferiore a quello dei suoi figli e, se così, scambiare il nodo con il più grande dei suoi figli.
Ripeti il passaggio 2 per ciascuno dei nodi non foglie che si avvicinano al mucchio. Quando raggiungi la radice dell'heap, l'intero heap dovrebbe ora essere un mucchio massimo.

Di seguito è riportato l'implementazione dell'approccio sopra:

C++

// A C++ program to convert min Heap to max Heap #include    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 node and heapify all internal  // nodes 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)  cout << arr[i] << ' '; } // Driver's code 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);  // Function call  convertMaxHeap(arr N);  printf('nMax Heap array : ');  printArray(arr N);  return 0; }

// C program to convert min Heap to max Heap #include  void swap(int* a int* b) {  int temp = *a;  *a = *b;  *b = temp; } // 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 node and heapify all internal  // nodes 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's code 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);  // Function call  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 node and heapify all internal  // nodes 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's code  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);  // Function call  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 node and heapify all # internal nodes 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) # Function call convertMaxHeap(arr N) print('Max Heap array : ') printArray(arr N) # This code is contributed by PranchalK

// 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 node and  // heapify all internal nodes  // 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's 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);  // Function call  convertMaxHeap(arr n);  Console.Write('nMax Heap array : ');  printArray(arr n);  } } // This code is contributed by nitin mittal.

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 node and heapify all internal  // nodes 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('  
Max Heap array : '); printArray(arr n); // This code is contributed by 29AjayKumar  </script>

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 node and heapify all internal // nodes 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 ?>

Produzione

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

Complessità temporale: O (n) per i dettagli, consultare: Complessità temporale di costruire un mucchio
Spazio ausiliario: SU)

TechCodeview

Convertire il mucchio di min in un mucchio massimo