Эффективно объединяйте отсортированные последовательности Java

1. Обзор

В этом коротком руководстве мы увидим, как можно эффективно объединить отсортированные массивы с помощью кучи.

2. Алгоритм

Поскольку наша постановка задачи заключается в использовании кучи для объединения массивов, мы будем использовать мини-кучу для решения нашей проблемы. Минимальная куча — это не что иное, как бинарное дерево, в котором значение каждого узла меньше значений его дочерних узлов .

Обычно min-heap реализуется с использованием массива, в котором массив удовлетворяет определенным правилам, когда речь идет о поиске родителя и потомка узла.

Для массива A[] и элемента с индексом i :

• A[(i-1)/2] вернет своего родителя
• A[(2*i)+1] вернет левого дочернего элемента
• A[(2*i)+2] вернет правильный дочерний элемент

Вот изображение min-heap и его представления в виде массива:

Давайте теперь создадим наш алгоритм, который объединяет набор отсортированных массивов:

1. Создайте массив для хранения результатов, размер которого определяется путем сложения длины всех входных массивов.
2. Создайте второй массив размером, равным количеству входных массивов, и заполните его первыми элементами всех входных массивов.
3. Преобразуйте ранее созданный массив в мини-кучу, применив правила минимальной кучи ко всем узлам и их дочерним элементам.
4. Повторяйте следующие шаги, пока массив результатов не будет полностью заполнен.
5. Получите корневой элемент из минимальной кучи и сохраните его в массиве результатов.
6. Замените корневой элемент следующим элементом из массива, в котором находится текущий корень.
7. Снова примените правило минимальной кучи к нашему массиву минимальной кучи.

В нашем алгоритме есть рекурсивный поток для создания минимальной кучи, и мы должны посетить все элементы входных массивов .

Временная сложность этого алгоритма равна O(k log n) , где k — общее количество элементов во всех входных массивах, а n — общее количество отсортированных массивов .

Давайте теперь посмотрим пример ввода и ожидаемый результат после запуска алгоритма, чтобы мы могли лучше понять проблему. Итак, для этих массивов:

{ { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } }

Алгоритм должен вернуть массив результатов:

{ 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 }

3. Реализация Java

Теперь, когда у нас есть общее представление о том, что такое мини-куча и как работает алгоритм слияния, давайте посмотрим на реализацию Java. Мы будем использовать два класса — один для представления узлов кучи, а другой для реализации алгоритма слияния.

3.1. Представление узла кучи

Перед реализацией самого алгоритма создадим класс, представляющий узел кучи. Это сохранит значение узла и два вспомогательных поля:

public class HeapNode {

    int element;
    int arrayIndex;
    int nextElementIndex = 1;

    public HeapNode(int element, int arrayIndex) {
        this.element = element;
        this.arrayIndex = arrayIndex;
    }
}

Обратите внимание, что мы намеренно опустили здесь геттеры и сеттеры , чтобы упростить задачу. Мы будем использовать свойство arrayIndex для хранения индекса массива, в котором берется текущий элемент узла кучи. И мы будем использовать свойство nextElementIndex для хранения индекса элемента, который мы возьмем после перемещения корневого узла в результирующий массив.

Изначально значение nextElementIndex будет равно 1 . Мы будем увеличивать его значение после замены корневого узла min-heap.

3.2. Алгоритм слияния с минимальной кучей

Наш следующий класс должен представлять саму мини-кучу и реализовывать алгоритм слияния:

public class MinHeap {

    HeapNode[] heapNodes;

    public MinHeap(HeapNode heapNodes[]) {
        this.heapNodes = heapNodes;
        heapifyFromLastLeafsParent();
    }

    int getParentNodeIndex(int index) {
        return (index - 1) / 2;
    }

    int getLeftNodeIndex(int index) {
        return (2 * index + 1);
    }

    int getRightNodeIndex(int index) {
        return (2 * index + 2);
    }

    HeapNode getRootNode() {
        return heapNodes[0];
    }

    // additional implementation methods
}

Теперь, когда мы создали наш класс min-heap, давайте добавим метод, который будет увеличивать поддерево, где корневой узел поддерева находится в заданном индексе массива:

void heapify(int index) {
    int leftNodeIndex = getLeftNodeIndex(index);
    int rightNodeIndex = getRightNodeIndex(index);
    int smallestElementIndex = index;
    if (leftNodeIndex < heapNodes.length 
      && heapNodes[leftNodeIndex].element < heapNodes[index].element) {
        smallestElementIndex = leftNodeIndex;
    }
    if (rightNodeIndex < heapNodes.length
      && heapNodes[rightNodeIndex].element < heapNodes[smallestElementIndex].element) {
        smallestElementIndex = rightNodeIndex;
    }
    if (smallestElementIndex != index) {
        swap(index, smallestElementIndex);
        heapify(smallestElementIndex);
    }
}

Когда мы используем массив для представления минимальной кучи, последний листовой узел всегда будет в конце массива. Таким образом, при преобразовании массива в мини-кучу путем итеративного вызова метода heapify() нам нужно только начать итерацию с родительского узла последнего листа:

void heapifyFromLastLeafsParent() {
    int lastLeafsParentIndex = getParentNodeIndex(heapNodes.length);
    while (lastLeafsParentIndex >= 0) {
        heapify(lastLeafsParentIndex);
        lastLeafsParentIndex--;
    }
}

Наш следующий метод будет выполнять фактическую реализацию нашего алгоритма. Для лучшего понимания давайте разделим метод на две части и посмотрим, как он работает:

int[] merge(int[][] array) {
    // transform input arrays
    // run the minheap algorithm
    // return the resulting array
}

Первая часть преобразует входные массивы в массив узлов кучи, который содержит все элементы первого массива, и находит размер результирующего массива:

HeapNode[] heapNodes = new HeapNode[array.length];
int resultingArraySize = 0;

for (int i = 0; i < array.length; i++) {
    HeapNode node = new HeapNode(array[i][0], i);
    heapNodes[i] = node;
    resultingArraySize += array[i].length;
}

И следующая часть заполняет массив результатов, реализуя шаги 4, 5, 6 и 7 нашего алгоритма:

MinHeap minHeap = new MinHeap(heapNodes);
int[] resultingArray = new int[resultingArraySize];

for (int i = 0; i < resultingArraySize; i++) {
    HeapNode root = minHeap.getRootNode();
    resultingArray[i] = root.element;

    if (root.nextElementIndex < array[root.arrayIndex].length) {
        root.element = array[root.arrayIndex][root.nextElementIndex++];
    } else {
        root.element = Integer.MAX_VALUE;
    }
    minHeap.heapify(0);
}

4. Тестирование алгоритма

Давайте теперь протестируем наш алгоритм с теми же входными данными, которые мы упоминали ранее:

int[][] inputArray = { { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } };
int[] expectedArray = { 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 };

int[] resultArray = MinHeap.merge(inputArray);

assertThat(resultArray.length, is(equalTo(10)));
assertThat(resultArray, is(equalTo(expectedArray)));

5. Вывод

В этом уроке мы узнали, как эффективно объединять отсортированные массивы с помощью min-heap.

Пример, который мы здесь продемонстрировали, можно найти на GitHub .