0

我有一个包含最大堆的数组表示。对于 '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， ETC）？

4

1 回答 1

1

我认为你有一个 MIN 堆而不是 MAX 堆。

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

最小堆保证以下内容：

  1. 根始终是最小值（在您的情况下为元素 0）
  2. 树总是左序的（对于任何堆都是如此）

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

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

编辑： 如果在您的情况下您考虑给予“a”比“b”更高的优先级，那么是的，您确实有一个 MAX 堆。

于 2012-11-08T04:52:53.273 回答