java - 使用 ArrayList 进行 Heapify

Question

我编写了这个方法来测试我的优先级队列，它有一个 ArrayList 和一个比较器作为参数:

@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(队列的新根)。这些是方法extract 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;
  }

这是整数比较器:

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

建议，考虑在索引 0 处添加一个未使用的元素，以便更直观地访问每个节点的父节点/子节点。

示例:

考虑堆 heap = [-1, 6, 4, 5, 2, 1, 4, 3]，其中根定义为 heap[1] ，堆的数据位于从 index = 1 到堆的大小之间。

要访问 index 处节点的子节点，直观地说，左子节点定义为 heap[2 * index] ，右子节点定义为定义为堆[2 *索引+ 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

这将使您在 extractMax() 时仅丢失 1 个元素

希望有帮助!