java如何检查max heap children以找出哪个更大

Question

我有一个保存最大堆的数组表示。对于一个由'd'，'b'，'c'组成的数组，它的值是：b，d，c，虽然它应该是b，c，d。这是我的加法：

public boolean add (E e) {
  ensureCapacity(objectCount + 1);
  pq[objectCount++] = e;

  //percolate up
  for (int i = objectCount - 1; i >= 0; i--) {
     if (priorityComparator.compare(pq[i], pq[parent(i)]) >= 0) {
          E tmp = pq[parent(i)];
          pq[parent(i)] = pq[i];
          pq[i] = tmp;

     }
  }

  modCount++;

  return true;
  }

如果我接下来添加“a”，它将成功更改为a、b、c、d。我如何修复该方法，以便它检查左子级（2*I+1）和右子级（2*I+2），并根据哪个队列具有更高的优先级（a的优先级高于b，等等）交换它们的值

Answer 1

我认为你有一个最小堆，而不是最大堆

我没有看过你的代码，但是：

最小堆保证了以下几点：

1. 根始终是min（在您的例子中是元素0）
2. 树始终保持左有序（对于任何堆都是如此）

输出b，d，c在你的情况下是完全合法的。尝试删除b并再次调用heapify，输出将是c，d

维基链接：http://en.wikipedia.org/wiki/Binary_heap

编辑： 如果在你的情况下，你认为给予“A”比“B”更高的优先级，那么是的，你确实有一个最大堆。p>