Перейти к основному содержимому

Как реализовать кучи Min-Max в Java

· 8 мин. чтения

Задача: Наибольшая подстрока без повторений

Для заданной строки s, найдите длину наибольшей подстроки без повторяющихся символов. Подстрока — это непрерывная непустая последовательность символов внутри строки...

ANDROMEDA 42

1. Обзор

В этом руководстве мы рассмотрим, как реализовать кучу min-max в Java.

2. Мин-макс куча

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

./5fc023c0351757158d0648a5bf16b947.png

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

Каждый узел в куче min-max имеет элемент данных, который обычно называется ключом. Корень имеет наименьший ключ в куче min-max, а один из двух узлов на втором уровне является наибольшим ключом . Для каждого узла, такого как X , в куче min-max: ``

  • Если X находится на минимальном (или даже) уровне, то X.key является минимальным ключом среди всех ключей в поддереве с корнем X.
  • Если X находится на максимальном (или нечетном) уровне, то X.key является максимальным ключом среди всех ключей в поддереве с корнем X.

Подобно min-heap или max-heap, вставка и удаление могут происходить с временной сложностью O (logN) .

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

Давайте начнем с простого класса, представляющего нашу минимальную кучу:

public class MinMaxHeap<T extends Comparable<T>> {
private List<T> array;
private int capacity;
private int indicator;
}

Как видно выше, мы используем индикатор для определения индекса последнего элемента, добавленного в массив. Но прежде чем мы продолжим, нам нужно помнить, что индекс массива начинается с нуля, но мы предполагаем, что индекс начинается с единицы в куче.

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

private int getLeftChildIndex(int i) {
return 2 * i;
}

private int getRightChildIndex(int i) {
return ((2 * i) + 1);
}

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

private int getParentIndex(int i) {
return i / 2;
}

private int getGrandparentIndex(int i) {
return i / 4;
}

Теперь давайте продолжим работу над нашим простым классом минимальной и максимальной кучи:

public class MinMaxHeap<T extends Comparable<T>> {
private List<T> array;
private int capacity;
private int indicator;

MinMaxHeap(int capacity) {
array = new ArrayList<>();
this.capacity = capacity;
indicator = 1;
}

MinMaxHeap(List<T> array) {
this.array = array;
this.capacity = array.size();
this.indicator = array.size() + 1;
}
}

Здесь мы можем создать экземпляр кучи min-max двумя способами. Во- первых, мы инициируем массив с ArrayList и определенной емкостью, а во-вторых, мы делаем минимальную кучу из существующего массива.

Теперь давайте обсудим операции с нашей кучей.

3.1. Создавать

Давайте сначала рассмотрим создание кучи min-max из существующего массива. Здесь мы используем алгоритм Флойда с некоторой адаптацией, такой как алгоритм Heapify :

public List<T> create() {
for (int i = Math.floorDiv(array.size(), 2); i >= 1; i--) {
pushDown(array, i);
}
return array;
}

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

private void pushDown(List<T> array, int i) {
if (isEvenLevel(i)) {
pushDownMin(array, i);
} else {
pushDownMax(array, i);
}
}

Как видим, для всех четных уровней мы проверяем элементы массива с помощью pushDownMin. Этот алгоритм подобен heapify-down, который мы будем использовать для removeMin и removeMax :

private void pushDownMin(List<T> h, int i) {
while (getLeftChildIndex(i) < indicator) {
int indexOfSmallest = getIndexOfSmallestChildOrGrandChild(h, i);
//...
i = indexOfSmallest;
}
}

Во-первых, мы находим индекс наименьшего потомка или внука элемента ' i' . Далее действуем согласно следующим условиям.

Если наименьший дочерний элемент или внук не меньше текущего элемента, мы ломаемся. Другими словами, текущее расположение элементов похоже на min-heap:

if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
//...
} else {
break;
}

Если наименьший дочерний или внучатый элемент меньше текущего элемента, мы меняем его местами с его родителем или прародителем:

if (getParentIndex(getParentIndex(indexOfSmallest)) == i) {
if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
swap(indexOfSmallest - 1, i - 1, h);
if (h.get(indexOfSmallest - 1)
.compareTo(h.get(getParentIndex(indexOfSmallest) - 1)) > 0) {
swap(indexOfSmallest - 1, getParentIndex(indexOfSmallest) - 1, h);
}
}
} else if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
swap(indexOfSmallest - 1, i - 1, h);
}

Мы продолжим описанные выше операции, пока не найдем дочерний элемент для элемента «i».

Теперь давайте посмотрим, как работает getIndexOfSmallestChildOrGrandChild . Это довольно легко! Во-первых, мы предполагаем, что левый дочерний элемент имеет наименьшее значение, а затем сравниваем его с другими:

private int getIndexOfSmallestChildOrGrandChild(List<T> h, int i) {
int minIndex = getLeftChildIndex(i);
T minValue = h.get(minIndex - 1);
// rest of the implementation
}

На каждом шаге, если индекс больше индикатора, ответом является последнее найденное минимальное значение.

Например, давайте сравним min-value с правым дочерним элементом:

if (getRightChildIndex(i) < indicator) {
if (h.get(getRightChildIndex(i) - 1).compareTo(minValue) < 0) {
minValue = h.get(getRightChildIndex(i));
minIndex = getRightChildIndex(i);
}
} else {
return minIndex;
}

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

@Test
public void givenUnOrderedArray_WhenCreateMinMaxHeap_ThenIsEqualWithMinMaxHeapOrdered() {
List<Integer> list = Arrays.asList(34, 12, 28, 9, 30, 19, 1, 40);
MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap<>(list);
minMaxHeap.create();
Assert.assertEquals(List.of(1, 40, 34, 9, 30, 19, 28, 12), list);
}

Алгоритм для pushDownMax идентичен алгоритму для pushDownMin , но при всех сравнениях операторы меняются местами.

3.2. Вставлять

Давайте посмотрим, как добавить элемент в кучу min-max:

public void insert(T item) {
if (isEmpty()) {
array.add(item);
indicator++;
} else if (!isFull()) {
array.add(item);
pushUp(array, indicator);
indicator++;
} else {
throw new RuntimeException("invalid operation !!!");
}
}

Во-первых, мы проверяем, пуста куча или нет. Если куча пуста, добавляем новый элемент и увеличиваем показатель. В противном случае добавленный новый элемент может изменить порядок кучи min-max, поэтому нам нужно настроить кучу с помощью pushUp :

private void pushUp(List<T>h,int i) {
if (i != 1) {
if (isEvenLevel(i)) {
if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) < 0) {
pushUpMin(h, i);
} else {
swap(i - 1, getParentIndex(i) - 1, h);
i = getParentIndex(i);
pushUpMax(h, i);
}
} else if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) > 0) {
pushUpMax(h, i);
} else {
swap(i - 1, getParentIndex(i) - 1, h);
i = getParentIndex(i);
pushUpMin(h, i);
}
}
}

Как мы видим выше, новый элемент сравнивает своего родителя, затем:

  • Если обнаружено, что он меньше (больше), чем родитель, то он определенно меньше (больше), чем все остальные элементы на максимальных (минимальных) уровнях, которые находятся на пути к корню кучи.
  • Путь от нового элемента к корню (учитывая только минимальные/максимальные уровни) должен быть в порядке убывания (возрастания), как это было до вставки. Итак, нам нужно сделать бинарную вставку нового элемента в эту последовательность

Теперь давайте посмотрим на pushUpMin следующим образом:

private void pushUpMin(List<T> h , int i) {
while(hasGrandparent(i) && h.get(i - 1)
.compareTo(h.get(getGrandparentIndex(i) - 1)) < 0) {
swap(i - 1, getGrandparentIndex(i) - 1, h);
i = getGrandparentIndex(i);
}
}

Технически проще поменять местами новый элемент с его родителем, пока родитель больше. Кроме того, pushUpMax идентичен pushUpMin , но при всех сравнениях операторы меняются местами.

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

@Test
public void givenNewElement_WhenInserted_ThenIsEqualWithMinMaxHeapOrdered() {
MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap(8);
minMaxHeap.insert(34);
minMaxHeap.insert(12);
minMaxHeap.insert(28);
minMaxHeap.insert(9);
minMaxHeap.insert(30);
minMaxHeap.insert(19);
minMaxHeap.insert(1);
minMaxHeap.insert(40);
Assert.assertEquals(List.of(1, 40, 28, 12, 30, 19, 9, 34),
minMaxHeap.getMinMaxHeap());
}

3.3. Найти мин.

Основной элемент в куче min-max всегда находится в корне, поэтому мы можем найти его за временную сложность O(1):

public T min() {
if (!isEmpty()) {
return array.get(0);
}
return null;
}

3.4. Найдите Макса

Максимальный элемент в куче min-max всегда находится на первом нечетном уровне, поэтому мы можем найти его за временную сложность O (1) с помощью простого сравнения:

public T max() {
if (!isEmpty()) {
if (indicator == 2) {
return array.get(0);
}
if (indicator == 3) {
return array.get(1);
}
return array.get(1).compareTo(array.get(2)) < 0 ? array.get(2) : array.get(1);
}
return null;
}

3.5. Удалить мин.

В этом случае мы найдем элемент min, а затем заменим его последним элементом массива:

public T removeMin() {
T min = min();
if (min != null) {
if (indicator == 2) {
array.remove(indicator--);
return min;
}
array.set(0, array.get(--indicator - 1));
array.remove(indicator - 1);
pushDown(array, 1);
}
return min;
}

3.6. Удалить Макс

Удаление элемента max аналогично удалению min, с той лишь разницей, что мы находим индекс элемента max, а затем вызываем pushDown :

public T removeMax() {
T max = max();
if (max != null) {
int maxIndex;
if (indicator == 2) {
maxIndex = 0;
array.remove(--indicator - 1);
return max;
} else if (indicator == 3) {
maxIndex = 1;
array.remove(--indicator - 1);
return max;
} else {
maxIndex = array.get(1).compareTo(array.get(2)) < 0 ? 2 : 1;
}
array.set(maxIndex, array.get(--indicator - 1));
array.remove(indicator - 1);
pushDown(array, maxIndex + 1);
}
return max;
}

4. Вывод

В этом руководстве мы рассмотрели реализацию кучи min-max в Java и изучили некоторые из наиболее распространенных операций.

Во-первых, мы узнали, что такое куча min-max, включая некоторые из наиболее распространенных функций. Затем мы увидели, как создавать, вставлять, находить-минимум, находить-макс, удалять-минимум и удалять-макс элементы в нашей реализации кучи min-max.

Как обычно, все примеры, использованные в этой статье, доступны на GitHub .