Рубрики

Сортировка номеров, хранящихся на разных машинах

Дано N машин. Каждая машина содержит несколько чисел в отсортированном виде. Но количество номеров у каждой машины не фиксированное. Выведите числа со всей машины в отсортированном неубывающем виде.
Пример:

       Machine M1 contains 3 numbers: {30, 40, 50}
       Machine M2 contains 2 numbers: {35, 45} 
       Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
       
       Output: {10, 30, 35, 40, 45, 50, 60, 70, 80, 100}

Представление потока чисел на каждой машине рассматривается как связанный список. Min Heap может использоваться для печати всех чисел в отсортированном порядке.

Ниже приводится подробный процесс

1. Сохраните указатели заголовков связанных списков в minHeap размера N, где N — количество машин.

2. Извлеките минимальный элемент из minHeap. Обновите minHeap, заменив заголовок minHeap следующим числом из связанного списка или заменив заголовок minHeap последним числом в minHeap, после чего уменьшите размер кучи на 1.

3. Повторяйте шаг 2 выше, пока куча не станет пустой.

Ниже приведена реализация вышеуказанного подхода на C ++.

// Программа, которая берет цифры с разных машин и печатает их в отсортированном порядке
#include <stdio.h>

  
// Узел связанного списка

struct ListNode

{

    int data;

    struct ListNode* next;

};

  
// Узел Min Heap

struct MinHeapNode

{

    ListNode* head;

};

  
// Min Heao (Коллекция узлов Min Heap)

struct MinHeap

{

    int count;

    int capacity;

    MinHeapNode* array;

};

  
// Функция для создания Min Heap заданной емкости

MinHeap* createMinHeap( int capacity )

{

    MinHeap* minHeap = new MinHeap;

    minHeap->capacity = capacity;

    minHeap->count = 0;

    minHeap->array = new MinHeapNode [minHeap->capacity];

    return minHeap;

}

  
/ * Утилита для вставки нового узла в начале

   связанного списка * /

void push (ListNode** head_ref, int new_data)

{

    / * выделить узел * /

    ListNode* new_node = new ListNode;

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref)    = new_node;

}

  
// Вспомогательная функция для замены двух минимальных узлов кучи. Эта функция
// нужен в minHeapify

void swap( MinHeapNode* a, MinHeapNode* b )

{

    MinHeapNode temp = *a;

    *a = *b;

    *b = temp;

}

  
// Стандартная функция minHeapify.

void minHeapify( MinHeap* minHeap, int idx )

{

    int left, right, smallest;

    left = 2 * idx + 1;

    right = 2 * idx + 2;

    smallest = idx;

  

    if ( left < minHeap->count &&

         minHeap->array[left].head->data <

         minHeap->array[smallest].head->data

       )

        smallest = left;

  

    if ( right < minHeap->count &&

         minHeap->array[right].head->data <

         minHeap->array[smallest].head->data

       )

        smallest = right;

  

    if( smallest != idx )

    {

        swap( &minHeap->array[smallest], &minHeap->array[idx] );

        minHeapify( minHeap, smallest );

    }

}

  
// Утилита для проверки того, является ли Min Heap пустым или нет

int isEmpty( MinHeap* minHeap )

{

    return (minHeap->count == 0);

}

  
// Стандартная функция для построения кучи

void buildMinHeap( MinHeap* minHeap )

{

    int i, n;

    n = minHeap->count  - 1;

    for( i = (n - 1) / 2; i >= 0; --i )

        minHeapify( minHeap, i );

}

  
// Эта функция вставляет элементы массива в кучу, а затем вызывает
// buildHeap для свойства кучи среди узлов

void populateMinHeap( MinHeap* minHeap, ListNode* *array, int n )

{

    for( int i = 0; i < n; ++i )

        minHeap->array[ minHeap->count++ ].head = array[i];

  

    buildMinHeap( minHeap );

}

  
// Возвращаем минимальный элемент из всех связанных списков
ListNode* extractMin( MinHeap* minHeap )
{

    if( isEmpty( minHeap ) )

         return NULL;

  

    // корень кучи будет иметь минимальное значение

    MinHeapNode temp = minHeap->array[0];

  

    // Заменить корень либо следующим узлом из того же списка.

    if( temp.head->next )

        minHeap->array[0].head = temp.head->next;

    else // Если список пуст, то уменьшить размер кучи

    {

        minHeap->array[0] = minHeap->array[ minHeap->count - 1 ];

        --minHeap->count;

    }

  

    minHeapify( minHeap, 0 );

    return temp.head;

}

  
// Основная функция, которая принимает массив списков с N машин
// и генерирует отсортированный вывод

void externalSort( ListNode *array[], int N )

{

    // Создаем минимальную кучу размером, равным количеству машин

    MinHeap* minHeap = createMinHeap( N );

  

    // заполнить первый элемент со всех машин

    populateMinHeap( minHeap, array, N );

  

    while ( !isEmpty( minHeap ) )

    {

        ListNode* temp = extractMin( minHeap );

        printf( "%d ",temp->data );

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int N = 3; // Количество машин

  

    // массив указателей, хранящих заголовочные узлы связанных списков

    ListNode *array[N];

  

    // Создаем связанный список 30-> 40-> 50 для первой машины

    array[0] = NULL;

    push (&array[0], 50);

    push (&array[0], 40);

    push (&array[0], 30);

  

    // Создаем связанный список 35-> 45 для второго компьютера

    array[1] = NULL;

    push (&array[1], 45);

    push (&array[1], 35);

  

    // Создание связанного списка 10-> 60-> 70-> 80 для третьего компьютера

    array[2] = NULL;

    push (&array[2], 100);

    push (&array[2], 80);

    push (&array[2], 70);

    push (&array[2], 60);

    push (&array[2], 10);

  

    // Сортировка всех элементов

    externalSort( array, N );

  

    return 0;

}

Выход:

10 30 35 40 45 50 60 70 80 100

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сортировка номеров, хранящихся на разных машинах

0.00 (0%) 0 votes