设计与分析最佳合并模式

将一组不同长度的排序文件合并为一个排序文件。我们需要找到一个最佳解决方案，在最短的时间内生成结果文件。

如果给定了已排序文件的数量，则有多种方法可以将它们合并为单个已排序文件。该合并可以成对执行。因此，这种类型的合并称为2 路合并模式。

由于不同的配对需要不同的时间，在此策略中，我们希望确定将多个文件合并在一起的最佳方式。在每一步中，两个最短的序列都会被合并。

要合并p 记录文件和q 记录文件可能需要p + q记录移动，明显的选择是在每一步将两个最小的文件合并在一起。

双向合并模式可以用二叉合并树来表示。让我们考虑一组n个排序文件{f ₁ , f ₂ , f ₃ , …, f _n }。最初，它的每个元素都被视为单节点二叉树。为了找到最佳解决方案，使用以下算法。

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

在该算法结束时，根节点的权重代表最优成本。

例子

让我们考虑给定的文件 f ₁、 f ₂、 f ₃、 f ₄和 f ₅，分别具有 20、30、10、5 和 30 个元素。

如果按照提供的顺序进行合并操作，则

M ₁ = 合并 f ₁和 f ₂ => 20 + 30 = 50

M ₂ = 合并 M ₁和 f ₃ => 50 + 10 = 60

M ₃ = 合并 M ₂和 f ₄ => 60 + 5 = 65

M ₄ = 合并 M ₃和 f ₅ => 65 + 30 = 95

因此，总操作次数为

50 + 60 + 65 + 95 = 270

那么现在问题来了，有没有更好的解决方案呢？

根据数字的大小升序对数字进行排序，我们得到以下序列 -

f ₄ , f ₃ , f ₁ , f ₂ , f ₅

因此，可以对该序列执行合并操作

M ₁ = 合并 f ₄和 f ₃ => 5 + 10 = 15

M ₂ = 合并 M ₁和 f ₁ => 15 + 20 = 35

M ₃ = 合并 M ₂和 f ₂ => 35 + 30 = 65

M ₄ = 合并 M ₃和 f ₅ => 65 + 30 = 95

因此，总操作次数为

15 + 35 + 65 + 95 = 210

显然，这比上一篇要好。

在这种情况下，我们现在将使用该算法来解决问题。

初始设定

步骤1

第2步

步骤3

步骤4

因此，该解决方案需要 15 + 35 + 60 + 95 = 205 次比较。

例子

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
int optimalMerge(int files[], int n)
{
    // Sort the files in ascending order
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (files[j] > files[j + 1]) {
                int temp = files[j];
                files[j] = files[j + 1];
                files[j + 1] = temp;
            }
        }
    }
    int cost = 0;
    while (n > 1) {
        // Merge the smallest two files
        int mergedFileSize = files[0] + files[1];
        cost += mergedFileSize;
        // Replace the first file with the merged file size
        files[0] = mergedFileSize;
        // Shift the remaining files to the left
        for (int i = 1; i < n - 1; i++) {
            files[i] = files[i + 1];
        }
        n--; // Reduce the number of files
        // Sort the files again
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    int temp = files[j];
                    files[j] = files[j + 1];
                    files[j + 1] = temp;
                }
            }
        }
    }
    return cost;
}
int main()
{
    int files[] = {5, 10, 20, 30, 30};
    int n = sizeof(files) / sizeof(files[0]);
    int minCost = optimalMerge(files, n);
    printf("Minimum cost of merging is: %d Comparisons\n", minCost);
    return 0;
}

输出

Minimum cost of merging is: 205 Comparisons

#include <iostream>
#include <algorithm>
int optimalMerge(int files[], int n) {
    // Sort the files in ascending order
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (files[j] > files[j + 1]) {
                std::swap(files[j], files[j + 1]);
            }
        }
    }
    int cost = 0;
    while (n > 1) {
        // Merge the smallest two files
        int mergedFileSize = files[0] + files[1];
        cost += mergedFileSize;
        // Replace the first file with the merged file size
        files[0] = mergedFileSize;
        // Shift the remaining files to the left
        for (int i = 1; i < n - 1; i++) {
            files[i] = files[i + 1];
        }
        n--; // Reduce the number of files
        // Sort the files again
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    std::swap(files[j], files[j + 1]);
                }
            }
        }
    }
    return cost;
}
int main() {
    int files[] = {5, 10, 20, 30, 30};
    int n = sizeof(files) / sizeof(files[0]);
    int minCost = optimalMerge(files, n);
    std::cout << "Minimum cost of merging is: " << minCost << " Comparisons\n";
    return 0;
}

输出

Minimum cost of merging is: 205 Comparisons

import java.util.Arrays;
public class Main {
    public static int optimalMerge(int[] files, int n) {
        // Sort the files in ascending order
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    // Swap files[j] and files[j + 1]
                    int temp = files[j];
                    files[j] = files[j + 1];
                    files[j + 1] = temp;
                }
            }
        }
        int cost = 0;
        while (n > 1) {
            // Merge the smallest two files
            int mergedFileSize = files[0] + files[1];
            cost += mergedFileSize;
            // Replace the first file with the merged file size
            files[0] = mergedFileSize;
            // Shift the remaining files to the left
            for (int i = 1; i < n - 1; i++) {
                files[i] = files[i + 1];
            }
            n--; // Reduce the number of files
            // Sort the files again
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < n - i - 1; j++) {
                    if (files[j] > files[j + 1]) {
                        // Swap files[j] and files[j + 1]
                        int temp = files[j];
                        files[j] = files[j + 1];
                        files[j + 1] = temp;
                    }
                }
            }
        }
        return cost;
    }
    public static void main(String[] args) {
        int[] files = {5, 10, 20, 30, 30};
        int n = files.length;
        int minCost = optimalMerge(files, n);
        System.out.println("Minimum cost of merging is: " + minCost + " Comparisons");
    }
}

输出

Minimum cost of merging is: 205 Comparison

def optimal_merge(files):
    # Sort the files in ascending order
    files.sort()
    cost = 0
    while len(files) > 1:
        # Merge the smallest two files
        merged_file_size = files[0] + files[1]
        cost += merged_file_size
        # Replace the first file with the merged file size
        files[0] = merged_file_size
        # Remove the second file
        files.pop(1)
        # Sort the files again
        files.sort()
    return cost
files = [5, 10, 20, 30, 30]
min_cost = optimal_merge(files)
print("Minimum cost of merging is:", min_cost, "Comparisons")

输出

Minimum cost of merging is: 205 Comparisons