Удаление из индексированной очереди приоритетов (Java)

Question

У меня есть индексированная очередь с минимальным приоритетом, реализованная в виде кучи.При удалении индексированного элемента код:

 public void delete(int i) {
    if (i < 0 || i >= maxN) throw new IllegalArgumentException();
    if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
    int index = qp[i];
    exch(index, n--);
    swim(index); // Why is this needed?
    sink(index);
    keys[i] = null;
    qp[i] = -1;
}

Остальной код можно найти здесь: https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

, поскольку pq[N] является последним элементом в * 1008.*, и это поменяно местами с элементом в pq[i] (который должен быть удален), не будет ли это означать, что значение в pq[i] после свопа больше или равно pq[i] перед свопом?Вопрос в том, почему мы должны вообще звонить swim(i), а не только sink(i)?При каких конкретных условиях необходимо звонить swim(i) после обмена?

(Есть 3 массива, qp[] и keys[] с соответствующими индексами и pq[], таких что qp[pq[i]] = pq[qp[i]] = i.)

Answer 1

Поскольку pq [N] является последним элементом в pq [], и он заменяется на элемент в pq [i] (который должен быть удален), это не означает, что значение в pq[i] после того, как своп больше или равен pq [i] до свопа?

Нет, это не обязательно так.Единственное требование для правильной кучи - это то, что ребенок не может быть больше, чем его родитель.Хотя это означает, что элемент в первой позиции является наименьшим, это означает, что не означает, что элемент в последней позиции является самым большим.Рассмотрим следующую кучу:

                1
      10                 2  
  15       18        5        3
16  17   19  20    7   8    6   4

pq[N] - это 4, и все же в этой куче много элементов, которые больше ее.Предположим, мы хотели удалить 15, заменив его на 4.4 меньше, чем 10, поэтому его нужно будет перемещать вверх по дереву (используя swim).