对存储在不同机器上的数字进行排序

---

在当今数据量庞大且系统互联互通的世界中，大量数据在各种机器上创建和存储。一个具有挑战性的问题是如何对存储在多台设备上的这些数据进行排序。排序作为计算中的一个基本操作，用于优化数据的检索、搜索和分析。但是，随着分布式系统和各种互连机器的出现，这项排序任务变得既困难又重要。

问题陈述

给定一个包含 N 个链表的数组，这些链表代表 N 台不同的机器。每个链表包含一些数量可变的数字，这些数字按升序排列。任务是按升序返回存储在这些 N 台机器上的所有数字。

示例 1

输入

Machine 1: 1, 4, 10
Machine 2: 2, 7, 8, 9

输出

1, 2, 4, 7, 8, 9, 10

解释

机器中的最小数字是 1，然后是下一个最大的数字。最后，我们得到 10 作为最大数字。

示例 2

输入

Machine 1: 1, 5
Machine 2: 2, 7, 8, 9
Machine 3: 3, 4, 12
Machine 4: 0, 6, 15

输出

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15

解释

机器中的最小数字是 0，然后是下一个最大的数字。最后，我们得到 15 作为最大数字。

解决方案：最小堆

可以使用最小堆来获取存储在不同机器上的排序数字。创建一个最小堆，首先只插入链表的头部，并提取最小元素。获取最小元素后，推送已删除节点的下一个节点。重复上述步骤以获取数字的排序顺序。

伪代码

define a structure named node:
   data: integer
   next: node pointer
define a structure named compare:
   define a function operator() that takes two node pointers a and b:
      return a->data > b->data
define a function named new_node that takes an integer data:
   node = create a new node
   node.data = data
   node.next = null
   return node
define a function named push that takes a node pointer head and an integer data:
   if head is null:
      head = new_node(data)
   else:
      node = new_node(data)
      node.next = head
      head = node
define a function named sort_on_diff_machines that takes an array of node pointers arr and an integer N:
   create a vector of node pointers named lists from arr[0] to arr[N-1]
   ptr = new_node(0)
   q = ptr
   create a priority queue named min_heap with compare comparator
   for each node pointer list in lists:
      if list is not null:
         push list into min_heap
   while min_heap is not empty:
      node = pop the top node from min_heap
      connect q's next to node
      q = q's next
      if node's next is not null:
         push node's next into min_heap
   res = ptr's next
   while res is not null:
      print res's data
      move res to res's next

示例：C++ 实现

以下代码对存储在不同机器上的数字进行排序。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Structure of node of linked list
struct Node {
   int data;
   Node *next;
};
// Comparator used by priority queue
struct Compare {
   bool operator()(const Node *a, const Node *b) {
      return a->data > b->data;
   }
};
// Helper function to create a new node in linked list
Node *newNode(int data) {
   Node *node = new Node;
   node->data = data;
   node->next = nullptr;
   return node;
}
// Helper function to create array of linked list by adding numbers
void push(Node **head, int data) {
   if (*head == nullptr) {
      *head = newNode(data);
   }
   else {
      Node *node = newNode(data);
      node->next = *head;
      *head = node;
   }
}
// Function to sort number son various machines
void sortOnDiffMachines(Node *arr[], int N) {
   vector<Node *> lists(arr, arr + N);
   Node *ptr = newNode(0);
   Node *q = ptr;
   priority_queue<Node *, vector<Node *>, Compare> minHeap;
   for (Node *list : lists) {
      if (list != nullptr) {
         minHeap.push(list);
      }
   }
   while (!minHeap.empty()) {
      Node *node = minHeap.top();
      minHeap.pop();
      q->next = node;
      q = q->next;
      if (node->next != nullptr) {
         minHeap.push(node->next);
      }
   }
   Node *res = ptr->next;
   while (res != nullptr) {
      cout << res->data << " ";
      res = res->next;
   }
}
int main() {
   int N = 2;
   Node *arr[N];
   arr[0] = nullptr;
   push(&arr[0], 10);
   push(&arr[0], 4);
   push(&arr[0], 1);
   arr[1] = nullptr;
   push(&arr[1], 9);
   push(&arr[1], 8);
   push(&arr[1], 7);
   push(&arr[1], 2);
   sortOnDiffMachines(arr, N);
   return 0;
}

输出

1 2 4 7 8 9 10

时间复杂度 - O(N * logN)，其中 N 是机器的数量。

空间复杂度 - O(N)

结论

总之，给定的解决方案有效地解决了对存储在不同机器上的数字进行排序的问题。通过使用各种数据结构，如链表和优先级队列，该解决方案合并了不同的列表并对它们进行排序。提供的解决方案提供了 O(N * logN) 的时间复杂度和 O(N) 的空间复杂度。