KONVERTER MIN BUNKE TIL MAX HEAP

Givet en matrixrepræsentation af Min Heap konverter den til Max Heap.

Eksempler:

java hovedmetode

Input: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ /
12 18 9
Produktion: arr [] = {20 18 10 12 9 9 3 5 6 8}

20
/
18 10
//
12 9 3
/ /
5 6 8
Input: arr [] = {3 4 8 11 13}
Produktion: arr [] = {13 11 8 4 3}
kanel vs makker

Ideen er simpelthen at opbygge Max Heap uden at bekymre sig om input. Start fra den nederste og mest højre interne knudepunkt for min-heap og bølger alle interne knudepunkter i bottom-up måde for at bygge den maksimale bunke.

Følg de givne trin for at løse problemet:

Ring til heapify-funktionen fra den højre interne knudepunkt på min-heap
Heapify alle interne knudepunkter i bottom-up måde at opbygge Max Heap
Udskriv max-heap

Algoritme: Her er en Algoritme til konvertering af en min heap til en maksimal bunke :

Start ved den sidste ikke-bladsknudepunkt for dyngen (dvs. forælderen til den sidste bladknude). For en binær bunke er denne knude placeret på indeksbunden ((n - 1)/2), hvor n er antallet af knudepunkter i dyngen.
For hver ikke-blad knude skal du udføre en 'Heapify' Betjening for at fikse heap -egenskaben. I en min. Heap involverer denne operation at kontrollere, om værdien af noden er større end for børnene, og hvis det er tilfældet med at bytte noden med det mindre af sine børn. I en maksimal bunke involverer operationen kontrol af, om værdien af noden er mindre end for dens børn, og hvis det er tilfældet med at bytte noden med den større af sine børn.
Gentag trin 2 for hver af de ikke-bladknudepunkter, der arbejder dig op ad bunken. Når du når roden af dyngen, skal hele bunken nu være en maksimal bunke.

Nedenfor er implementeringen af ovenstående tilgang:

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 ?>

Produktion

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

Tidskompleksitet: O (n) For detaljer henvises til: henvis: Tidskompleksitet ved at bygge en bunke
Hjælprum: O (n)

TechCodeview

Konverter min bunke til Max Heap