KONVERTĒT MIN HEAP UZ MAX HEAP

Ņemot vērā Min Heap masīva attēlojumu, pārveidojiet to par Max Heap.

Piemēri:

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

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

Ideja ir vienkārši veidot Max Heap, nerūpējoties par ieguldījumu. Sāciet no apakšējā un visglabākējā mīnā esošā iekšējā mezgla un kaudzē visus iekšējos mezglus no apakšas augšup, lai izveidotu maksimālo kaudzi.

Veiciet dotos pasākumus, lai atrisinātu problēmu:

Zvaniet uz Heapify funkciju no Mine-Choap labējā iekšējā mezgla
Kaudzējiet visus iekšējos mezglus no apakšas augšup, lai izveidotu Max Heap
Izdrukājiet maksimāli-heap

Algoritms: Lūk Algoritms minimāla kaudzes konvertēšanai uz maksimālu kaudzi :

Sāciet no kaudzes pēdējās ne lapu mezgla (t.i., pēdējā lapu mezgla vecāks). Binārai kaudzei šis mezgls atrodas indeksa grīdā ((n - 1)/2), kur n ir mezglu skaits kaudzē.
Katram mezglam, kas nav lapas "kaudze" darbība, lai labotu kaudzes īpašumu. Min kaudzē šī operācija ietver pārbaudi, vai mezgla vērtība ir lielāka nekā tā bērnu vērtība, un vai tā ir mezgla apmainīšana ar mazāko bērnu. Maksimālajā kaudzē operācija ietver pārbaudi, vai mezgla vērtība ir mazāka nekā tā bērniem, un vai tā mezgla apmainīšana ar lielāko bērnu.
Atkārtojiet 2. soli katram no lapām, kas nav lapu mezgli, kas darbojas augšup pa kaudzi. Kad jūs sasniedzat kaudzes sakni, visai kaudzei tagad vajadzētu būt maksimālai kaudzei.

Zemāk ir iepriekš minētās pieejas ieviešana:

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

Izvade

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

Laika sarežģītība: O (n) Lai iegūtu sīkāku informāciju, lūdzu, skatiet: Kaudzes veidošanas laika sarežģītība
Papildu telpa: O (n)

TechCodeview

Konvertēt Min Heap uz Max Heap