Heapify с ArrayList

Question

Я написал этот метод для проверки своей очереди приоритетов, в которой в качестве параметра указан ArrayList и Comparator:

@Test
  public void testPriorityQueue_ExtractMax() {
    PriorityQueue queue = new PriorityQueue(new IntegerComparator());
    Integer[] arrayExp={14, 9};
    queue.insert(16);
    queue.insert(9);
    queue.insert(14);
    queue.extractMax();
    assertArrayEquals(arrayExp, queue.getArray().toArray());
  }

Теперь, если я его выполняю, он говорит, что первые элементы в моем результате равны 9, но мне должно быть 14 (новый корень моей очереди).Это методы извлечение max и heapify .Как я могу решить это?

public void heapify(int index) {
    int largest = index;
    int leftIndex = 2 * index + 1;
    int rightIndex = 2 * index + 2;

    if (leftIndex < queue.size() && c.compare(queue.get(index), (queue.get(leftIndex))) < 0)
      largest = leftIndex;

    if (rightIndex < queue.size() && c.compare(queue.get(largest), queue.get(rightIndex)) < 0)
      largest = rightIndex;

    if (largest != index) {
      swap(index, largest);
      heapify(largest);
    }
  }

  public T extractMax() {
    if (queue.size() == 0) return null;

    T min = queue.get(0);
    queue.remove(0);
    queue.set(0, queue.get(queue.size() - 1));
    heapify(0);
    return min;
  }

Это IntegerComparator:

public class IntegerComparator implements Comparator<Integer>{
  @Override
  public int compare(Integer l1, Integer l2) {
    int result = l1.compareTo(l2);
    if(result != 0)
      return result;
    return -1;
   }
}

EDIT_2: Это мой метод вставки, может ли это быть проблема:

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

Answer 1

При этом queue.remove(i); автоматически сдвигает все элементы после индекса i влево на одну позицию.

https://www.tutorialspoint.com/java/util/arraylist_remove.htm

И с queue.set(0, queue.get(queue.size() - 1)); Вы просто устанавливаете значение последнего индекса из очереди на индекс 0 и теряете значение из индекса 0, но оно все еще остается на последней позиции.

После прочтения вставить метод

При queue.set(i, queue.get(parentIndex));, если i = queue.size() на первом шаге, это означает, что индекс, которого я не существует в очереди.

Answer 2

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

Пример

Рассмотрим кучу heap = [-1, 6, 4, 5, 2, 1, 4, 3], где корень определен как heap[1], а данные для кучи расположены от index = 1 до размера кучи.

Чтобы получить доступ к дочерним узлам на index, интуитивно понятно, что левый дочерний элемент определен как heap[2 * index], а правый дочерний элемент определен как heap[2 * index + 1]. Точно так же, чтобы получить доступ к родительскому узлу узла в index, можно использовать усечение int для доступа к родителям:

int parentInd = (int)(index/2);
T parent = heap[parentInd];

Решение

Как указывал raul1ro, вы теряете данные из индекса 0, которые вы не собирались удалять.

В extractMax():

T min = queue.get(0);
queue.remove(0);
queue.set(0, queue.get(queue.size() - 1));

должно быть:

T min = queue.get(0); //Get min
T temp = queue.get(queue.size() - 1); //Get the last element in heap as temp
queue.remove(queue.size - 1); //Remove the last element
queue.set(0, temp); //Set the root to the temp value so that you can heapify

Это сделает так, что вы потеряете только 1 элемент, когда вы extractMax()

Надеюсь, это поможет!