«1. Обзор
В этом коротком руководстве мы увидим, как можно эффективно объединить отсортированные массивы с помощью кучи.
2. Алгоритм
Поскольку наша постановка задачи заключается в использовании кучи для слияния массивов, мы будем использовать мини-кучу для решения нашей задачи. Минимальная куча — это не что иное, как бинарное дерево, в котором значение каждого узла меньше значений его дочерних узлов.
Обычно min-heap реализуется с использованием массива, в котором массив удовлетворяет определенным правилам, когда речь идет о поиске родителя и потомка узла.
Для массива A[] и элемента с индексом i:
-
A[(i-1)/2] вернет своего родителя A[(2*i)+1] вернет левого дочернего элемента A[ (2*i)+2] вернет правильный дочерний элемент
Вот изображение min-heap и его представление в виде массива:
Давайте теперь создадим наш алгоритм, который объединяет набор отсортированных массивов:
- Create an array to store the results, with the size determined by adding the length of all the input arrays.
- Create a second array of size equal to the number of input arrays, and populate it with the first elements of all the input arrays.
- Transform the previously created array into a min-heap by applying the min-heap rules on all nodes and their children.
- Repeat the next steps until the result array is fully populated.
- Get the root element from the min-heap and store it in the result array.
- Replace the root element with the next element from the array in which the current root is populated.
- Apply min-heap rule again on our min-heap array.
Наш алгоритм имеет рекурсивный поток для создания минимальной кучи, и мы должны посетить все элементы входных массивов.
Временная сложность этого алгоритма равна 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
}
Теперь, когда мы создали наш класс с минимальной кучей, давайте добавим метод, который будет куча поддерева, где корневой узел поддерева находится в заданном индексе массива:
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. Заключение
В этом руководстве мы узнали, как эффективно объединять отсортированные массивы с помощью минимальной кучи.
Пример, который мы здесь продемонстрировали, можно найти на GitHub.