Combine dos arrays ordenadas en O (1) espacio adicional usando Heap

Dadas dos arrays ordenadas , arr[] , brr[] de tamaño N y M , la tarea es fusionar las dos arrays dadas de modo que formen una secuencia ordenada de enteros que combinen elementos de ambas arrays.

Ejemplos:

Entrada: arr[] = {10}, brr[] = {2, 3}
Salida : 2 3 10
Explicación: La array ordenada combinada obtenida al tomar todos los elementos de ambas arrays es {2, 3, 10}. 
Por lo tanto, la salida requerida es 2 3 10.

Entrada: arr[]= {1, 5, 9, 10, 15, 20}, brr[] = {2, 3, 8, 13}
Salida: 1 2 3 5 8 9 10 13 15 20

Enfoque ingenuo: Consulte Fusionar dos arrays ordenadas para obtener el enfoque más simple para fusionar las dos arrays dadas.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)

Enfoque optimizado para el espacio: Consulte Fusionar dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)

Enfoque de optimización de espacio eficiente: consulte Fusionar de manera eficiente dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de tiempo: O((N + M) * log(N + M))
Espacio auxiliar: O(1)

Enfoque basado en montón : el problema se puede resolver usando Heap . La idea es recorrer la array arr[] y comparar el valor de arr[i] con brr[0] y verificar si arr[i] es mayor que brr[0] o no. Si se determina que es cierto, entonces swap(arr[i], brr[0) y realice laoperación heapify en brr[] . Siga los pasos a continuación para resolver el problema:

  • Recorra la array arr[] y compare el valor de arr[i] con brr[0] y verifique si arr[i] es mayor que brr[0] o no. Si se determina que es cierto, entonces swap(arr[i], brr[0) y realice la operación heapify en brr[] .
  • Finalmente, ordene la array brr[] e imprima ambas arrays.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform min heapify
// on array brr[]
void minHeapify(int brr[], int i, int M)
{
 
    // Stores index of left child
    // of i.
    int left = 2 * i + 1;
 
    // Stores index of right child
    // of i.
    int right = 2 * i + 2;
 
    // Stores index of the smallest element
    // in (arr[i], arr[left], arr[right])
    int smallest = i;
 
    // Check if arr[left] less than
    // arr[smallest]
    if (left < M && brr[left] < brr[smallest]) {
 
        // Update smallest
        smallest = left;
    }
 
    // Check if arr[right] less than
    // arr[smallest]
    if (right < M && brr[right] < brr[smallest]) {
 
        // Update smallest
        smallest = right;
    }
 
    // if i is not the index
    // of smallest element
    if (smallest != i) {
 
        // Swap arr[i] and arr[smallest]
        swap(brr[i], brr[smallest]);
 
        // Perform heapify on smallest
        minHeapify(brr, smallest, M);
    }
}
 
// Function to merge two sorted arrays
void merge(int arr[], int brr[],
           int N, int M)
{
 
    // Traverse the array arr[]
    for (int i = 0; i < N; ++i) {
 
        // Check if current element
        // is less than brr[0]
        if (arr[i] > brr[0]) {
 
            // Swap arr[i] and brr[0]
            swap(arr[i], brr[0]);
 
            // Perform heapify on brr[]
            minHeapify(brr, 0, M);
        }
    }
 
    // Sort array brr[]
    sort(brr, brr + M);
}
 
// Function to print array elements
void printArray(int arr[], int N)
{
 
    // Traverse array arr[]
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 23, 35, 235, 2335 };
    int brr[] = { 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = sizeof(brr) / sizeof(brr[0]);
 
    // Function call to merge
    // two array
    merge(arr, brr, N, M);
 
    // Print first array
    printArray(arr, N);
 
    // Print Second array.
    printArray(brr, M);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to perform
// min heapify on array
// brr[]
static void minHeapify(int brr[],
                       int i, int M)
{
  // Stores index of left
  // child of i.
  int left = 2 * i + 1;
 
  // Stores index of right
  // child of i.
  int right = 2 * i + 2;
 
  // Stores index of the smallest
  // element in (arr[i], arr[left],
  // arr[right])
  int smallest = i;
 
  // Check if arr[left] less than
  // arr[smallest]
  if (left < M && brr[left] <
      brr[smallest])
  {
    // Update smallest
    smallest = left;
  }
 
  // Check if arr[right] less
  // than arr[smallest]
  if (right < M && brr[right] <
      brr[smallest])
  {
    // Update smallest
    smallest = right;
  }
 
  // if i is not the index
  // of smallest element
  if (smallest != i)
  {
    // Swap arr[i] and
    // arr[smallest]
    int temp = brr[i];
    brr[i] =  brr[smallest];
    brr[smallest] = temp;
 
    // Perform heapify on smallest
    minHeapify(brr, smallest, M);
  }
}
 
// Function to merge two
// sorted arrays
static void merge(int arr[], int brr[],
                  int N, int M)
{
  // Traverse the array arr[]
  for (int i = 0; i < N; ++i)
  {
    // Check if current element
    // is less than brr[0]
    if (arr[i] > brr[0])
    {
      // Swap arr[i] and brr[0]
      int temp = arr[i];
      arr[i] = brr[0];
      brr[0] = temp;
 
      // Perform heapify on brr[]
      minHeapify(brr, 0, M);
    }
  }
 
  // Sort array brr[]
  Arrays.sort(brr);
}
 
// Function to print array
// elements
static void printArray(int arr[],
                       int N)
{
  // Traverse array arr[]
  for (int i = 0; i < N; i++)
    System.out.print(arr[i] + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {2, 23, 35, 235, 2335};
  int brr[] = {3, 5};
  int N = arr.length;
  int M = brr.length;
 
  // Function call to merge
  // two array
  merge(arr, brr, N, M);
 
  // Print first array
  printArray(arr, N);
 
  // Print Second array.
  printArray(brr, M);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to implement
# the above approach
 
# Function to perform min heapify
# on array brr[]
def minHeapify(brr, i, M):
 
    # Stores index of left child
    # of i.
    left = 2 * i + 1
 
    # Stores index of right child
    # of i.
    right = 2 * i + 2
 
    # Stores index of the smallest element
    # in (arr[i], arr[left], arr[right])
    smallest = i
 
    # Check if arr[left] less than
    # arr[smallest]
    if (left < M and brr[left] < brr[smallest]):
 
        # Update smallest
        smallest = left
 
    # Check if arr[right] less than
    # arr[smallest]
    if (right < M and brr[right] < brr[smallest]):
 
        # Update smallest
        smallest = right
 
    # If i is not the index
    # of smallest element
    if (smallest != i):
 
        # Swap arr[i] and arr[smallest]
        brr[i], brr[smallest] = brr[smallest], brr[i]
 
        # Perform heapify on smallest
        minHeapify(brr, smallest, M)
 
# Function to merge two sorted arrays
def merge(arr, brr, N, M):
 
    # Traverse the array arr[]
    for i in range(N):
 
        # Check if current element
        # is less than brr[0]
        if (arr[i] > brr[0]):
 
            # Swap arr[i] and brr[0]
            arr[i], brr[0] = brr[0], arr[i]
 
            # Perform heapify on brr[]
            minHeapify(brr, 0, M)
 
    # Sort array brr[]
    brr.sort()
 
# Function to print array elements
def printArray(arr, N):
 
    # Traverse array arr[]
    for i in range(N):
        print(arr[i], end = " ")
 
# Driver code
if __name__ == '__main__':
 
    arr = [ 2, 23, 35, 235, 2335 ]
    brr = [3, 5]
    N = len(arr)
    M = len(brr)
 
    # Function call to merge
    # two array
    merge(arr, brr, N, M)
 
    # Print first array
    printArray(arr, N)
 
    # Print Second array.
    printArray(brr, M)
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to perform
// min heapify on array
// brr[]
static void minHeapify(int []brr,
                       int i, int M)
{
   
  // Stores index of left
  // child of i.
  int left = 2 * i + 1;
 
  // Stores index of right
  // child of i.
  int right = 2 * i + 2;
 
  // Stores index of the smallest
  // element in (arr[i], arr[left],
  // arr[right])
  int smallest = i;
 
  // Check if arr[left] less than
  // arr[smallest]
  if (left < M && brr[left] <
      brr[smallest])
  {
     
    // Update smallest
    smallest = left;
  }
 
  // Check if arr[right] less
  // than arr[smallest]
  if (right < M && brr[right] <
      brr[smallest])
  {
     
    // Update smallest
    smallest = right;
  }
 
  // If i is not the index
  // of smallest element
  if (smallest != i)
  {
     
    // Swap arr[i] and
    // arr[smallest]
    int temp = brr[i];
    brr[i] =  brr[smallest];
    brr[smallest] = temp;
 
    // Perform heapify on smallest
    minHeapify(brr, smallest, M);
  }
}
 
// Function to merge two
// sorted arrays
static void merge(int []arr, int[]brr,
                  int N, int M)
{
   
  // Traverse the array []arr
  for(int i = 0; i < N; ++i)
  {
     
    // Check if current element
    // is less than brr[0]
    if (arr[i] > brr[0])
    {
       
      // Swap arr[i] and brr[0]
      int temp = arr[i];
      arr[i] = brr[0];
      brr[0] = temp;
 
      // Perform heapify on brr[]
      minHeapify(brr, 0, M);
    }
  }
 
  // Sort array brr[]
  Array.Sort(brr);
}
 
// Function to print array
// elements
static void printArray(int []arr,
                       int N)
{
   
  // Traverse array []arr
  for(int i = 0; i < N; i++)
    Console.Write(arr[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = { 2, 23, 35, 235, 2335 };
  int []brr = {3, 5};
  int N = arr.Length;
  int M = brr.Length;
 
  // Function call to merge
  // two array
  merge(arr, brr, N, M);
 
  // Print first array
  printArray(arr, N);
 
  // Print Second array.
  printArray(brr, M);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to perform min heapify
// on array brr[]
function minHeapify(brr, i, M)
{
 
    // Stores index of left child
    // of i.
    let left = 2 * i + 1;
 
    // Stores index of right child
    // of i.
    let right = 2 * i + 2;
 
    // Stores index of the smallest element
    // in (arr[i], arr[left], arr[right])
    let smallest = i;
 
    // Check if arr[left] less than
    // arr[smallest]
    if (left < M && brr[left] < brr[smallest]) {
 
        // Update smallest
        smallest = left;
    }
 
    // Check if arr[right] less than
    // arr[smallest]
    if (right < M && brr[right] < brr[smallest]) {
 
        // Update smallest
        smallest = right;
    }
 
    // if i is not the index
    // of smallest element
    if (smallest != i) {
 
        // Swap arr[i] and arr[smallest]
        let temp = brr[i];
        brr[i] =  brr[smallest];
        brr[smallest] = temp;
  
 
        // Perform heapify on smallest
        minHeapify(brr, smallest, M);
    }
}
 
// Function to merge two sorted arrays
function merge(arr, brr,
        N, M)
{
 
    // Traverse the array arr[]
    for (let i = 0; i < N; ++i) {
 
        // Check if current element
        // is less than brr[0]
        if (arr[i] > brr[0]) {
 
            // Swap arr[i] and brr[0]
            let temp = arr[i];
              arr[i] = brr[0];
              brr[0] = temp;
  
 
            // Perform heapify on brr[]
            minHeapify(brr, 0, M);
        }
    }
 
    // Sort array brr[]
    brr.sort();
}
 
// Function to print array elements
function printArray(arr, N)
{
 
    // Traverse array arr[]
    for (let i = 0; i < N; i++)
        document.write(arr[i] + " ");
}
 
// Driver Code
 
    let arr = [ 2, 23, 35, 235, 2335 ];
    let brr = [ 3, 5 ];
    let N = arr.length;
    let M = brr.length;
 
    // Function call to merge
    // two array
    merge(arr, brr, N, M);
 
    // Print first array
    printArray(arr, N);
 
    // Print Second array.
    printArray(brr, M);
 
 
//This code is contributed by Mayank Tyagi
</script>
Producción: 

2 3 5 23 35 235 2335

 

Complejidad de tiempo: O((N + M) * log (M))
Espacio auxiliar: O(1)

Enfoque eficiente: Consulte fusionar dos arrays ordenadas para fusionar de manera eficiente las dos arrays dadas.
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M) 

Publicación traducida automáticamente

Artículo escrito por sanjay035 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *