對儲存在不同機器上的數字進行排序

---

在當今資料量龐大且系統互聯互通的世界中，大量資料在各種機器上建立和儲存。一個具有挑戰性的問題是如何對儲存在多臺裝置上的這些資料進行排序。排序作為計算中的一個基本操作，用於最佳化資料的檢索、搜尋和分析。但是，隨著分散式系統和各種互連機器的出現，這項排序任務變得既困難又重要。

問題陳述

給定一個包含 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) 的空間複雜度。