Max Heap с ArrayList

Question

Я создал класс для управления Приоритетной очередью с параметром ArrayList. Мне нужно сделать Max Heap, поэтому, если я сделаю следующую вставку: 16, 9, 7, 8, 4, 14, 1, 3, 2, 10, мне нужно получить ArrayList с этими элементами в этой позиции: {16 , 9, 14, 7, 4, 8, 10, 3, 2, 1}. Проблема в том, что мой метод вставки выглядит так, как будто не упорядочивает элементы:

public void insert(T elem) {
    int i = queue.size();
    int parentIndex = (int) Math.floor((i - 1) / 2);
    while (i > 0 && elem.compareTo(queue.get(parentIndex)) == 1) {
      queue.set(i, queue.get(parentIndex));
      i = parentIndex;
      parentIndex = (int) Math.floor((i - 1) / 2);
    }
    queue.add(i, elem);
  }

Пример: вставка (16), вставка (14), вставка (9). Ожидается массив: {16,9,14}. Результат: {16,14,9}.

Answer 1

Ваши ожидания нереальны. {16, 14, 9} - это совершенно допустимая двоичная куча.

Бинарная куча должна поддерживать два свойства:

1. Свойство shape - это полное двоичное дерево: дерево, в котором все уровни, кроме, возможно, последнего, полностью заполнены. Если не заполнен, последний уровень заполняется слева.
2. Свойство кучи. В максимальной куче каждый узел больше или равен своим дочерним элементам. В минимальной куче каждый узел меньше или равен своим дочерним элементам.

Итак, все это допустимые двоичные максимальные кучи из 4 элементов:

      4          4          4
    2   3      3   2      3   1
   1          1          2

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

Порядок узлов в двоичной куче зависит от порядка вставки. В вашем примере, если бы порядок вставки был {16, 9, 14}, то вы получили бы ожидаемый вами порядок.

См. https://en.wikipedia.org/wiki/Binary_heap для получения дополнительной информации о двоичных кучах.

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

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