にいくつかの問題がありますheapifyHelper:
public void heapifyHelper(int rootIndex) {
if(isLeafIndex(rootIndex)) {
return;
}
else {
int leftChildIndex = getLeftChildIndex(rootIndex);
int rightChildIndex = getRightChildIndex(rootIndex);
int leftChildValue = heap[leftChildIndex];
int rightChildValue = heap[rightChildIndex];
もしもleftChildIndex == heap.length - 1？その後、rightChildValueが発生しArrayIndexOutOfBoundsExceptionます。
int rootValue = heap[rootIndex];
if(leftChildValue < rootValue && leftChildValue < rightChildValue) {
swap(rootIndex, leftChildIndex);
heapifyHelper(leftChildIndex);
heapifyHelper(rightChildIndex);
}
else if(rightChildValue < rootValue && rightChildValue < leftChildValue) {
両方の子が等しく、親よりも小さい場合はどうなりますか? その場合、まったく交換しません。
swap(rootIndex, rightChildIndex);
heapifyHelper(leftChildIndex);
heapifyHelper(rightChildIndex);
}
}
}
[11, 4, 5]サブツリーに到達しない理由はheapifyHelper、子の 1 つが親よりも小さい場合にのみ子を呼び出すためですが、 を呼び出すとheapifyHelper(1)、ノードの 2 つの子5はと で9あり11、両方ともルート値よりも大きいためです。(実際には、は両方の子よりも小さいheapifyHelper(1)ため、を呼び出すことさえしません。)heap[0]
heapifyしかし、無条件に (存在する子に対して) 繰り返すことによってそれを修正するだけでは、正しいとは言えません。根から葉に繰り返した場合、各値は最大で 1 レベルまで上昇します。葉から根(1)まで繰り返す必要があり、値を 1 レベルだけでなく完全にふるいにかける必要があります。
値をその子の 1 つとのみ交換する場合、各位置は最大 2 回と見なされます。親と比較するときに 1 回、子と比較するときに 1 回。ルートからリーフに移動するとき、位置をその子と比較すると、その上の位置 (インデックスが小さい位置でさえも) を変更することはできなくなります。
そのため、各値は最大 1 レベルでバブルアップできます。最小の要素がルートの直接の子の下にある場合、ルートはツリー内の最小の要素にはなりません。葉 (またはむしろ葉の親) から開始すると、必要なだけ値が膨らむ可能性があります。ただし、値をその子の小さい方とのみ交換する場合 (それが値より小さい場合)、各値は 1 レベルしかバブルダウンできず、ヒープを作成する必要はありません。
木を考えてみましょう
7
/ \
/ \
2 6
/ \ / \
1 3 4 5
根から葉に行く場合は、交換2して7最初に、
2
/ \
/ \
7 6
/ \ / \
1 3 4 5
上位 2 つのレベルが最小ヒープになりました。
次に、左のサブツリーを処理し、最後に右のサブツリーを処理して、
2
/ \
/ \
1 4
/ \ / \
7 3 6 5
完全に。現在、下の 2 つのレベルは最小ヒープで構成されていますが、ヒープ プロパティは上のレベルで破棄されています。それを再びヒープにするには、1さらにふるいにかける必要があります (この場合は 1 レベルだけ)。
葉から根に行く場合は、まず右のサブツリーを扱います。
6
/ \
4 5
生産
4
/ \
6 5
そのために、左のサブツリー
2
/ \
1 3
生産
1
/ \
2 3
そこの。両方のサブツリーが最小ヒープになりました。全体として、あなたは持っています
7
/ \
/ \
1 4
/ \ / \
2 3 6 5
次に、 と を交換7し1、生成します
1
/ \
/ \
7 4
/ \ / \
2 3 6 5
ルートが最小値になりましたが、最後のスワップで左側のサブツリーのヒープ プロパティが破壊されました。それを再びヒープにするには、7さらにふるいにかける必要があります。
したがって、値を必要なだけ下 (上) にふるいにかけるsiftDownメソッド (および/またはメソッド) が必要です。siftUp
private void siftDown(int index) {
int leftChildIndex = getLeftChildIndex(index);
if (leftChildIndex >= heap.length) {
// a leaf, no further sifting down possible
return;
}
int rightChildIndex = getRightChildIndex(index);
if ((heap[leftChildIndex] < heap[index])
&& (rightChildIndex >= heap.length || heap[rightChildIndex] >= heap[leftChildIndex)) {
// left child is smallest or only, and smaller than parent
swap(index, leftChildIndex);
siftDown(leftChildIndex);
} else
// left child not smaller than parent, or right child exists and is smaller than parent
if (rightChildIndex < heap.length && heap[rightChildIndex] < heap[index]) {
swap(index, rightChildIndex);
siftDown(rightChildIndex);
}
// otherwise, this one has no smaller child, so no more sifting needed
}
次に、正しいものは次のheapifyようになります
public void heapify() {
// last index that has a child:
int lastNonLeafIndex = heap.length/2 - 1;
for(int index = lastNonLeafIndex; index >= 0; --index) {
siftDown(index);
}
}
これが機能するのは、両方のサブツリーが最小ヒープである (バイナリ) ツリーがある場合、ルート値をふるいにかけると最小ヒープが構築されるためです。
- ルート値が両方の子より小さい (または等しい) 場合、ツリー全体がすでに最小ヒープです。
- それ以外の場合、ルート値がその子の小さい方と交換された後 (左の一般性を失うことなく)、他のサブツリーは変更されないため、最小ヒープのままです。そして、左の子はスワップ前の左サブツリーの最小値だったので、ルートの値はスワップ後のツリー全体の最小値です。ただし、スワッピングにより、左の子の最小ヒープ プロパティが破壊された可能性があります。しかし、左-左および左-右のサブツリーは変更されていないため、まだ最小ヒープのままです。そして、新しい左側のサブツリーは元のツリーよりも小さいため、帰納仮説によって、そのルート値をふるいにかけると、そこから最小ヒープが作成されます。したがって、ふるい分けが完了すると、ルートに最小値を持つツリーができ、その両方のサブツリーが最小ヒープ、つまり最小ヒープになります。
各リーフは自明に最小ヒープであるため、 で処理されるインデックスごとにheapify、そのインデックスをルートとするサブツリーが最小ヒープになります。
代わりに、次を使用しsiftUpます。
private void siftUp(int index) {
if (index == 0) return; // root, nothing to do
int parentIndex = getParentIndex(index); // see Note below
if (heap[index] < heap[parentIndex]) {
swap(index, parentIndex);
siftUp(parentIndex);
}
}
public void heapify() {
for(int index = 1; index < heap.length; ++index) {
siftUp(index);
}
}
のコードは、ここでは 2 つのノードのみが関与するsiftUpため、 for よりもはるかに短く、siftDown子インデックスが配列の外にあるかどうかを確認する必要はありません。しかし、heapifyはあまり効率的ではありません (脚注(1)を参照)。
siftUp新しい値をヒープに挿入するために使用されるメソッドです。したがって、これはすべての値 (ルート値を除く) を既存の最小ヒープに挿入することによってヒープを構築します [siftUp(index)が呼び出されると、配列の前の部分indexは既に最小ヒープです]。
注：あなたgetParentIndexは間違っています、
return (childIndex / 2) - 1;
index の親は で、1index-1の親は3です0。正しいのは です。
return (childIndex - 1) / 2;
(1)実際には、各値を必要なだけふるいにかければ、根から葉に進むことができます。[親の] 葉から根に向かうように heapify する方が効率的です。ルートからリーフに移動すると、レベルでk値2^kをバブルアップする必要がある場合があり、ヒープの構築が複雑になりますk。O(n*log n)[親の] リーフから上に進むと、レベルを下げる2^(log n - 1 - k)必要がある値があり、ヒープの構築がk複雑になります。O(n)