我目前正在开发一个我必须创建最大堆的项目。我目前正在使用我的教科书版本的堆有点看起来像:
public MaxHeap(int initialCapacity) {
if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
else
checkCapacity(initialCapacity);
@SuppressWarnings("unchecked")
T[] tempHeap = (T[]) new Comparable[initialCapacity + 1];
heap = tempHeap;
lastIndex = 0;
initialized = true;
}
public T getMax() {
checkInitialization();
T root = null;
if (!isEmpty())
root = heap[1];
return root;
}
public boolean isEmpty() {
return lastIndex < 1;
}
public int getSize() {
return lastIndex;
}
public void clear() {
checkInitialization();
while (lastIndex > -1) {
heap[lastIndex] = null;
lastIndex--;
}
lastIndex = 0;
}
public void add(T newEntry) {
checkInitialization();
int newIndex = lastIndex + 1;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
heap[newIndex] = heap[parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
}
heap[newIndex] = newEntry;
lastIndex++;
ensureCapacity();
}
public int getSwaps()
{
return swaps;
}
public T removeMax() {
checkInitialization();
T root = null;
if (!isEmpty()) {
root = heap[1];
heap[1] = heap[lastIndex];
lastIndex--;
reheap(1);
}
return root;
}
private void reheap(int rootIndex) {
boolean done = false;
T orphan = heap[rootIndex];
int leftChildIndex = 2 * rootIndex;
while (!done && (leftChildIndex <= lastIndex)) {
int largerChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
largerChildIndex = rightChildIndex;
}
if (orphan.compareTo(heap[largerChildIndex]) < 0) {
heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
} else
done = true;
}
heap[rootIndex] = orphan;
}
我是否应该计算多个地方的掉期并打印总金额,如果是这样,我会在哪里计算它们?我之前曾尝试在add方法中枚举swaps ++,但我不认为这是正确的方法。
您必须计算add(T newEntry)
方法和reHeap
方法中的交换,该方法是从removeMax
mathod调用的。
在reHeap
中,你从顶部开始,当你从removeMax中调用它时,删除max(在Max Heap情况下)你用最后一个元素替换root,然后你需要平衡堆。因此堆递归地下降到最后一级以平衡可能需要交换。
编辑:
在reHeap
的以下代码块中添加交换:
if (orphan.compareTo(heap[largerChildIndex]) < 0) {
heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
// increment the swap here as inside this block of reHeap only swap takes place.
swap++
}
这些是正确的实施方式吗?
所以add方法是:
public void add(T newEntry) {
checkInitialization();
int newIndex = lastIndex + 1;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
heap[newIndex] = heap[parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
swap++;
}
heap[newIndex] = newEntry;
lastIndex++;
ensureCapacity();
}
而重播将是:
private void reheap(int rootIndex) {
boolean done = false;
T orphan = heap[rootIndex];
int leftChildIndex = 2 * rootIndex;
while (!done && (leftChildIndex <= lastIndex)) {
int largerChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
largerChildIndex = rightChildIndex;
}
if (orphan.compareTo(heap[largerChildIndex]) < 0) {
heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
swap++;
} else
done = true;
}
heap[rootIndex] = orphan;
}