Annetaan, että min -kasan taulukon esitys muuntaa sen maksimiksi.
Esimerkkejä:
Tulo: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
-
5 9
/////
6 8 20 10
/ / / / /
12 18 9Lähtö: arr [] = {20 18 10 12 9 9 3 5 6 8}
20
-
18 10
/////
12 9 9 3
/ / / / /
5 6 8Tulo: arr [] = {3 4 8 11 13}
Lähtö: arr [] = {13 11 8 4 3}
Ajatuksena on yksinkertaisesti rakentaa Max Heap välittämättä syötteestä. Aloita Min-HEAP: n alhaimmasta ja oikealta sisäisestä solmusta ja kasaa kaikki sisäiset solmut alhaalta ylöspäin suuntautuvan tavan rakentamiseksi.
Noudata annettuja vaiheita ongelman ratkaisemiseksi:
- Soita Heapify-toiminto Min-HEAP: n oikeanpuoleisimmasta sisäisestä solmusta
- Kasaa kaikki sisäiset solmut alhaalta ylöspäin rakentaakseen enimmäiskasan
- Tulosta enimmäishalus
Algoritmi: Tässä on Algoritmi min -kasan muuntamiseksi maksimiksi -
- Aloita kasan viimeisestä ei-lehtien solmusta (ts. Viimeisen lehden solmun vanhemmasta). Binaarikasalle tämä solmu sijaitsee hakemistokerroksessa ((n - 1)/2), jossa n on kasan solmujen lukumäärä.
- Jokaiselle ei-lehtien solmulle suorita a 'Heapify' Käyttö kasanominaisuuden korjaamiseksi. Pienissä kasassa tämä toimenpide sisältää sen tarkistamisen, onko solmun arvo suurempi kuin sen lasten arvo ja jos niin vaihtamalla solmun pienempiin lastensa kanssa. Max -kasaan operaatio sisältää sen tarkistamisen, onko solmun arvo pienempi kuin sen lasten arvo ja jos niin vaihtamalla solmun suurempiin lapsistaan.
- Toista vaihe 2 jokaiselle ei-lehtien solmulle, jotka työskentelevät kasan ylöspäin. Kun saavutat kasan juuren, koko kasan tulisi nyt olla enimmäiskasa.
Alla on yllä olevan lähestymistavan toteuttaminen:
C++// A C++ program to convert min Heap to max Heap #include
// C program to convert min Heap to max Heap #include
// 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
# 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.
<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>
// 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 ?> Tulos
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
Ajan monimutkaisuus: O (n) Katso lisätietoja: Kasan rakentamisen ajan monimutkaisuus
Aputila: O (n)