Рубрики

Конвертировать Min Heap в Max Heap

Если задано представление массива min Heap, преобразуйте его в max Heap за O (n) раз.
Пример :

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


Output: arr[] = [20 18 10 12 9 9 3 5 6 8] OR 
       [any Max Heap formed from input elements]

         20
       /    \
     18      10
   /    \    /  \
  12     9  9    3
 /  \   /
5    6 8 

На первый взгляд проблема может показаться сложной. Но наша конечная цель — построить максимум кучи. Идея очень проста — мы просто собираем Max Heap, не заботясь о входе. Мы начинаем с самого нижнего и самого правого внутреннего режима min Heap и накапливаем все внутренние режимы снизу вверх, чтобы построить Max heap.

Ниже его реализация

C ++

// Программа на C ++ для преобразования min Heap в max Heap
#include<bits/stdc++.h>

using namespace std;

  
// сложить поддерево с корнем по заданному индексу

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);

    }

}

  
// Эта функция в основном строит максимальную кучу

void convertMaxHeap(int arr[], int n)

{

    // Начинаем с самого нижнего и самого правого

    // внутренний режим и накапливаем все внутренние

    // режимы снизу вверх

    for (int i = (n-2)/2; i >= 0; --i)

        MaxHeapify(arr, i, n);

}

  
// Утилита для печати заданного массива
// заданного размера

void printArray(int* arr, int size)

{

    for (int i = 0; i < size; ++i)

        printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // массив, представляющий 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);

  

    convertMaxHeap(arr, n);

  

    printf("\nMax Heap array : ");

    printArray(arr, n);

  

    return 0;

}

Джава

// Java-программа для преобразования min Heap в max Heap

  

class GFG 

{

    // Куча поддерева с корнем по заданному индексу

    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)

        {

            // поменять местами arr [i] и arr [самый большой]

            int temp = arr[i];

            arr[i] = arr[largest];

            arr[largest] = temp;

            MaxHeapify(arr, largest, n);

        }

    }

   

    // Эта функция в основном строит максимальную кучу

    static void convertMaxHeap(int arr[], int n)

    {

        // Начинаем с самого нижнего и самого правого

        // внутренний режим и накапливаем все внутренние

        // режимы снизу вверх

        for (int i = (n-2)/2; i >= 0; --i)

            MaxHeapify(arr, i, n);

    }

   

    // Утилита для печати заданного массива

    // заданного размера

    static void printArray(int arr[], int size)

    {

        for (int i = 0; i < size; ++i)

            System.out.print(arr[i]+" ");

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        // массив, представляющий 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);

   

        convertMaxHeap(arr, n);

   

        System.out.print("\nMax Heap array : ");

        printArray(arr, n);

    }

}

  
// Предоставлено Прамод Кумар

python3

# Программа Python3 для преобразования минимальной кучи
# до макс кучи

  
# накапливать поддерево с корнем
# по заданному индексу

def MaxHeapify(arr, i, n):

    l = 2 * i + 1

    r = 2 * i + 2

    largest =

    if l < n and arr[l] > arr[i]: 

        largest = l

    if r < n and arr[r] > arr[largest]: 

        largest =

    if largest != i:

        arr[i], arr[largest] = arr[largest], arr[i] 

        MaxHeapify(arr, largest, n)

  
# Эта функция в основном строит максимальную кучу

def convertMaxHeap(arr, n):

      

    # Начните с самого нижнего и самого правого

    # внутренний режим и куча всех

    # внутренние режимы снизу вверх

    for i in range(int((n - 2) / 2), -1, -1):

        MaxHeapify(arr, i, n)

  
# Полезная функция для печати
# заданный массив заданного размера

def printArray(arr, size):

    for i in range(size):

        print(arr[i], end = " ")

    print()

  
Код водителя

if __name__ == '__main__':

      

    # массив, представляющий Min Heap

    arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9

    n = len(arr)

  

    print("Min Heap array : "

    printArray(arr, n) 

  

    convertMaxHeap(arr, n) 

  

    print("Max Heap array : "

    printArray(arr, n)

  
# Этот код предоставлен PranchalK

C #

// C # программа для конвертации
// от кучи до макс кучи

using System;

  

class GFG 

{

    // Чтобы сложить поддерево с

    // корень по указанному индексу

    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)

        {

            // поменять местами arr [i] и arr [самый большой]

            int temp = arr[i];

            arr[i] = arr[largest];

            arr[largest] = temp;

            MaxHeapify(arr, largest, n);

        }

    }

  

    // Эта функция в основном

    // строит максимальную кучу

    static void convertMaxHeap(int []arr, 

                               int n)

    {

        // Начнем с самого нижнего и

        // крайний правый внутренний режим и

        // heapify все внутренние режимы

        // снизу вверх

        for (int i = (n - 2) / 2; i >= 0; --i)

            MaxHeapify(arr, i, n);

    }

  

    // Утилита для печати

    // заданный массив заданного размера

    static void printArray(int []arr, 

                           int size)

    {

        for (int i = 0; i < size; ++i)

            Console.Write(arr[i]+" ");

    }

      

    // Код драйвера

    public static void Main () 

    {

        // массив, представляющий 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);

  

        convertMaxHeap(arr, n);

  

        Console.Write("\nMax Heap array : ");

        printArray(arr, n);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для преобразования min Heap в max Heap

  
// функция обмена utlity

function swap(&$a,&$b)

{

    $tmp=$a;

    $a=$b;

    $b=$tmp;

}

  
// сложить поддерево с корнем по заданному индексу

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);

    }

}

  
// Эта функция в основном строит максимальную кучу

function convertMaxHeap(&$arr, $n)

{

    // Начинаем с самого нижнего и самого правого

    // внутренний режим и накапливаем все внутренние

    // режимы снизу вверх

    for ($i = (int)(($n-2)/2); $i >= 0; --$i)

        MaxHeapify($arr, $i, $n);

}

  
// Утилита для печати заданного массива
// заданного размера

function printArray($arr, $size)

{

    for ($i = 0; $i <$size; ++$i)

        print($arr[$i]." ");

}

  

    // Код драйвера

  

    // массив, представляющий 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);

  

  
// Этот код предоставлен mits
?>


Выход :

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 

Сложность вышеупомянутого решения может выглядеть как O (nLogn), но это O (n). См. Этот G-Fact для более подробной информации.

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Конвертировать Min Heap в Max Heap

0.00 (0%) 0 votes