PŘEVEĎTE MIN HEAP NA MAX HALDU

Vzhledem k reprezentaci pole Min Halte to převeďte na max haldu.

Příklady:

Vstup: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ /
12 18 9
Výstup: arr [] = {20 18 10 12 9 9 3 5 6 8}

20
/
18 10
//
12 9 3
/ /
5 6 8
Vstup: arr [] = {3 4 8 11 13}
Výstup: arr [] = {13 11 8 4 3}

Tato myšlenka je jednoduše postavit Max Heap, aniž by se starala o vstup. Začněte ze spodního a pravého vnitřního vnitřního uzlu min-heap a hromadí všechny vnitřní uzly ve způsobu zdola nahoru, abyste vytvořili maximální haldu.

Postupujte podle daných kroků a vyřešte problém:

Zavolejte funkci Heapify z pravého vnitřního uzlu Min-Heap
THE TEAPIFIFUJTE VŠECHNY VNITŘNÍ UDIS ve zdola nahoru, aby vytvořila Max Heap
Vytiskněte maximum

Algoritmus: Tady je Algoritmus pro převod min haldy na maximální hromadu :

Začněte na posledním uzlu Halde (tj. Na rodiči posledního listového uzlu). Pro binární haldu je tento uzel umístěn v indexovém patře ((n - 1)/2), kde n je počet uzlů v haldě.
Pro každý uzel bez listů proveďte a 'HELIPIFY' Operace pro opravu vlastnosti haldy. V min haldě tato operace zahrnuje kontrolu, zda je hodnota uzlu větší než hodnota jeho dětí, a pokud tak vyměňuje uzel s menšími z jeho dětí. V maximální haldě zahrnuje operace kontrola, zda je hodnota uzlu menší než hodnota jeho dětí, a pokud tak vyměňuje uzel s většími z jeho dětí.
Opakujte krok 2 pro každý z uzlů bez listů, které se vydávají po hromadě. Když dosáhnete kořene hromady, měla by být nyní celá hromada maximální halda.

Níže je uvedena implementace výše uvedeného přístupu:

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

Výstup

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

Složitost času: O (n) Podrobnosti najdete: Časová složitost budování hromady
Pomocný prostor: O (n)

TechCodeview

Převeďte Min Heap na max haldu