Opération de fusion K-way pour le tri par fusion

Question

J'ai des tableaux triés k, chacun avec n éléments, et j'ai besoin de les combiner en un seul tableau trié de k*n éléments. Comment puis-je implémenter la procédure de fusion pour le tri par fusion, en commençant par les deux premiers et le suivant, et ainsi de suite?

C'est ce que j'ai jusqu'à présent.

// implementing function to merge arrays (merge procedure for merge sort) 
    public int[] merge(int[][] array){ 
     int k = array.length; 
     int n = array[0].length; 

// final merged array 
     int[] mergedArray = new int[k*n]; 
     return mergedArray;  
    } 

    public static void main(String[]args){ 
    Merge obj = new Merge(); 
int[][] data= new int[][]{{2, 9, 15, 20}, 
           {6, 8, 9, 19}, 
           {5, 10, 18, 22}, 
           {8, 12, 15, 26}}; 
    int[] mergedArrayTest = obj.merge(data); 
    //printArray(mergedArrayTest); 
    } 

Answer 1

Au lieu de fusionner les deux sous-réseaux à la fois, vous pouvez fusionner tous k à la fois.

• Créer un tableau d'indices dans chaque sous-groupe. Initialement, chaque indice est zéro.
• Sur chacune des itérations k*n pour remplir le tableau fusionné, considérez la valeur de chaque sous-matrice à son index respectif et mémorisez la valeur minimale. (Ignorer un index s'il a déjà atteint la fin du sous-tableau.)
• Incrémenter l'index pointant sur la valeur minimale.

Cela fera:

// k-way merge operation 
public int[] merge(int[][] array){ 
    int k = array.length; 
    int n = array[0].length; 

    int[] mergedArray = new int[k*n]; 
    int[] indices = new int[k]; 
    for (int i = 0; i < mergedArray.length; ++i) { 
    int bestValue = -1, bestIndex = -1; 
    for (int j = 0; j < indices.length; ++j) { 
     int index = indices[j]; 
     if (index < n && (bestValue == -1 || array[j][index] < bestValue)) { 
     bestValue = array[j][index]; 
     bestIndex = j; 
     } 
    } 
    mergedArray[i] = bestValue; 
    indices[bestIndex] += 1; 
    } 

    return mergedArray; 
} 

Vous pouvez faire cette approche un peu plus efficace en supprimant les indices qui ont atteint la fin de leur sous-tableau. Cependant, cela laisse encore le temps d'exécution dans O (nk) parce que O (k) indices sont analysés nk fois.

Nous pouvons apporter une amélioration asymptotique du temps d'exécution en stockant les index dans un min-heap qui utilise la valeur de chaque index comme clé. Avec k indices, la taille du tas ne dépasse jamais k. Dans chacune des itérations nk, nous sautons sur le tas et repoussons au plus un élément. Ces opérations de tas coûtent chacune O (log k), de sorte que la durée totale est de O (nk log k).

import java.lang.*; 
import java.util.*; 
import java.io.*; 

class Candidate { 
    int id, index, value; 
    Candidate(int id, int index, int value) { 
    this.id = id; 
    this.index = index; 
    this.value = value; 
    } 
} 

class Heap { 
    ArrayList<Candidate> stack = new ArrayList<Candidate>(); 

    void push(Candidate current) { 
    // Add to last position in heap. 
    stack.add(current); 
    // Bubble up. 
    int n = stack.size(), 
     pos = n - 1; 
    while (pos != 0) { 
     int parent = (pos - 1)/2; 
     if (stack.get(parent).value <= current.value) { 
     return; 
     } 
     stack.set(pos, stack.get(parent)); 
     stack.set(parent, current); 
    } 
    } 

    Candidate pop() { 
    // Get top of heap. 
    if (stack.size() == 0) { 
     return null; 
    } 
    Candidate result = stack.get(0); 
    int n = stack.size(); 
    if (n == 1) { 
     stack.remove(0); 
     return result; 
    } 
    // Swap last element to top. 
    stack.set(0, stack.get(--n)); 
    Candidate current = stack.get(0); 
    stack.remove(n); 
    // Bubble down. 
    int pos = 0; 
    while (true) { 
     int left = 2 * pos + 1; 
     if (left >= n) { 
     return result; 
     } 
     int right = left + 1, 
      swapTo = -1; 
     if (current.value <= stack.get(left).value) { 
     if (right == n || current.value <= stack.get(right).value) { 
      return result; 
     } 
     swapTo = right; 
     } else { 
     if (right != n && stack.get(left).value > stack.get(right).value) { 
      swapTo = right; 
     } else { 
      swapTo = left; 
     } 
     } 
     stack.set(pos, stack.get(swapTo)); 
     stack.set(swapTo, current); 
     pos = swapTo; 
    } 
    } 
} 

public class Merge { 

    // k-way merge 
    public int[] merge(int[][] array){ 
    int k = array.length; 
    int n = array[0].length; 

    int[] mergedArray = new int[k*n]; 

    // Initialize heap with subarray number, index, and value. 
    Heap indexHeap = new Heap(); 
    for (int i = 0; i < k; ++i) { 
     indexHeap.push(new Candidate(i, 0, array[i][0])); 
    } 

    for (int i = 0; i < mergedArray.length; ++i) { 
     // Get the minimum value from the heap and augment the merged array. 
     Candidate best = indexHeap.pop(); 
     mergedArray[i] = best.value; 
     // Increment the index. If it's still valid, push it back onto the heap. 
     if (++best.index < array[best.id].length) { 
     best.value = array[best.id][best.index]; 
     indexHeap.push(best); 
     } 
    } 

    // Print out the merged array for testing purposes. 
    for (int i = 0; i < mergedArray.length; ++i) { 
     System.out.print(mergedArray[i] + " "); 
    } 
    System.out.println(); 
    return mergedArray; 
    } 

    public static void main(String[]args){ 
    Merge merge = new Merge(); 
    int[][] data= new int[][]{{2, 9, 15, 20}, 
           {6, 8, 9, 19}, 
           {5, 10, 18, 22}, 
           {8, 12, 15, 26}}; 
    int[] mergedArrayTest = merge.merge(data); 
    } 
}