在javascript中将多个排序序列合并为一个排序序列的算法

Question

我正在寻找一种算法来合并多个排序的序列,让我们说X排序的序列有n个元素,在javascript中放入一个排序的序列,你能提供一些例子吗？

注意:我不想使用任何库.试图解决https://icpc.kattis.com/problems/stacking

在条件下,合并排序数组所需的最小操作数是多少:

拆分:通过提升堆栈的任何顶部并将其放在一边以形成新堆栈,可以将单个堆栈拆分为两个堆栈.

加入:可以通过将一个堆叠放在另一个堆叠的顶部来连接两个堆栈.仅当顶部堆叠的底板不大于底部堆叠的顶板时才允许这样做,即,必须正确地订购连接的堆叠.

Answer 1

天真的方法是连接所有k序列,并对结果进行排序.但如果每个序列都有n元素,那么成本就是O(k*n*log(k*n)).太多了!

相反,您可以使用优先级队列或堆.像这样:

var sorted = [];
var pq = new MinPriorityQueue(function(a, b) {
  return a.number < b.number;
});
var indices = new Array(k).fill(0);
for (var i=0; i<k; ++i) if (sequences[i].length > 0) {
  pq.insert({number: sequences[i][0], sequence: i});
}
while (!pq.empty()) {
  var min = pq.findAndDeleteMin();
  sorted.push(min.number);
  ++indices[min.sequence];
  if (indices[min.sequence] < sequences[i].length) pq.insert({
    number: sequences[i][indices[min.sequence]],
    sequence: min.sequence
  });
}

优先级队列最多只包含多个k元素,每个序列一个.您将继续提取最小值,并在该序列中插入以下元素.

有了这个,成本将是:

• k*n插入k元素堆:O(k*n)
• k*nk元素堆中的删除:O(k*n*log(k))
• 每个数字的各种常量操作: O(k*n)

所以只有 O(k*n*log(k))

Answer 2

历史

这个问题已经解决了一个多世纪,回到了Hermann Hollerith和电子贺卡.大量的信用卡,例如人口普查产生的信用卡,通过将它们分成批次,对每个批次进行分类,然后合并分类的批次 - 所谓的 "合并排序"进行排序.你在1950年的科幻电影中看到旋转的那些磁带驱动器很可能将多个分类的磁带合并到一个磁带上.

算法

您可以在https://en.wikipedia.org/wiki/Merge_algorithm找到所需的所有算法.用JS编写这个很简单.有关N路合并的算法问题,请参阅更多信息.另请参阅这个问题,这个问题几乎完全相同,但我不确定任何答案都非常好.

天真的连续和度假方法甚至没有资格作为问题的答案.有点天真的接下来最小值从任何输入方法要好得多,但不是最优的,因为找到下一个输入来获取值需要花费更多的时间.这就是使用称为"最小堆"或"优先级队列"的最佳解决方案的原因.

简单的JS解决方案

这是一个真正的简单版本,除了能够看到它正在做什么之外,我没有声称要进行优化:

const data = [[1, 3, 5], [2, 4]];    

// Merge an array or pre-sorted arrays, based on the given sort criteria.
function merge(arrays, sortFunc) {
  let result = [], next;
   
  // Add an 'index' property to each array to keep track of where we are in it.
  arrays.forEach(array => array.index = 0);
 
  // Find the next array to pull from.
  // Just sort the list of arrays by their current value and take the first one.     
  function findNext() {
    return arrays.filter(array => array.index < array.length)
      .sort((a, b) => sortFunc(a[a.index], b[b.index]))[0];
  }

  // This is the heart of the algorithm.
  while (next = findNext()) result.push(next[next.index++]);

  return result;
}

function arithAscending(a, b) { return a - b; }

console.log(merge(data, arithAscending));

上面的代码index在每个输入数组上维护一个属性,以记住我们所处的位置.简单的替代方案是shift当轮到它被合并时,来自每个数组前面的元素,但这将是相当低效的.

优化查找要拉出的下一个数组

这个简单的实现findNext,为了找到从中拉出下一个值的数组,只需对第一个元素的输入列表进行排序,并在结果中获取第一个数组.您可以通过使用"min-heap"以排序顺序管理数组来优化此操作,这样就无需每次都使用它.min-heap是一个树,由节点组成,其中每个节点包含一个值,该值是下面所有值的最小值,左右节点给出额外的(更大)值,依此类推.您可以在此处找到有关min-heap的JS实现的信息.

发电机解决方案

将此作为生成器编写可能会稍微清晰一些,它将可迭代列表作为输入,包括数组.

// Test data.
const data = [[1, 3, 5], [2, 4]];

// Merge an array or pre-sorted arrays, based on the given sort criteria.
function* merge(iterables, sortFunc) {
  let next;

  // Create iterators, with "result" property to hold most recent result.
  const iterators = iterables.map(iterable => {
    const iterator = iterable[Symbol.iterator]();
    iterator.result = iterator.next();
    return iterator;
  });

  // Find the next iterator whose value to use.
  function findNext() {
    return iterators
      .filter(iterator => !iterator.result.done)
      .reduce((ret, cur) => !ret || cur.result.value < ret.result.value ? cur : ret, 
         null);
  }

  // This is the heart of the algorithm.
  while (next = findNext()) {
    yield next.result.value;
    next.result = next.next();
  }
}

function arithAscending(a, b) { return a - b; }

console.log(Array.from(merge(data, arithAscending)));