Автор оригинала: Tino Mulanchira Thomas.
1. Обзор
В этом коротком уроке мы увидим, как мы можем эффективно объединять сортированные массивы с помощью кучи.
2. Алгоритм
Поскольку наша задача состоит в том, чтобы использовать кучу для объединения массивов, мы будем использовать минимальную кучу для решения нашей проблемы. Минимальная куча-это не что иное, как двоичное дерево , в котором значение каждого узла меньше, чем значения его дочерних узлов .
Обычно минимальная куча реализуется с использованием массива, в котором массив удовлетворяет определенным правилам, когда дело доходит до поиска родительского и дочернего узлов.
Для массива A[] и элемента с индексом i :
- A[(i-1)/2] вернет своего родителя
- A[(2*i)+1] вернет левого ребенка
- A[(2*i)+2] вернет правильного ребенка
Вот изображение min-heap и его представление в массиве:
Теперь давайте создадим наш алгоритм, который объединяет набор отсортированных массивов:
- Создайте массив для хранения результатов, размер которого определяется путем добавления длины всех входных массивов.
- Создайте второй массив размером, равным количеству входных массивов, и заполните его первыми элементами всех входных массивов.
- Преобразуйте ранее созданный массив в минимальную кучу, применив правила минимальной кучи ко всем узлам и их дочерним элементам.
- Повторяйте следующие шаги до тех пор, пока результирующий массив не будет полностью заполнен.
- Получите корневой элемент из минимальной кучи и сохраните его в результирующем массиве.
- Замените корневой элемент следующим элементом из массива, в котором заполнен текущий корень.
- Снова примените правило минимальной кучи к нашему массиву минимальной кучи.
Наш алгоритм имеет рекурсивный поток для создания минимальной кучи, и мы должны посетить все элементы входных массивов .
Время сложность этого алгоритма равно 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;
}
}Обратите внимание, что мы намеренно опустили геттеры и сеттеры здесь, чтобы все было просто. Мы будем использовать свойство array Index для хранения индекса массива, в котором берется текущий элемент узла кучи. И мы будем использовать свойство next Element Index для хранения индекса элемента, который мы возьмем после перемещения корневого узла в результирующий массив.
Первоначально значение индекса следующего элемента будет равно 1 . Мы будем увеличивать его значение после замены корневого узла минимальной кучи.
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 .