間隔ヒープからの最小要素の削除

• インターバルヒープでは、最小の要素はルートノードの左側にある要素です。この要素は削除されて返されます。
• ルートノードの左側に作成された空席を埋めるために、最後のノードの要素が削除され、ルートノードに再度挿入されます。
• 次に、この要素は降順ノードのすべての左側の要素と連続して比較され、インターバルヒープのすべての条件が満たされるとプロセスが終了します。
• ノードの左側の要素がいずれかの段階で右側の要素よりも高くなった場合、2つの要素が交換され、さらに比較が実行されます。
• 最後に、ルートノードの左側に最小の要素が再び含まれます。

この手順は、次の方法でも説明できます-

最小要素の削除は、いくつかの方法で処理されます-

• インターバルヒープが空の場合、removeMin操作は失敗します。
• インターバルヒープに要素が1つしかない場合は、この要素を返す必要があります。要素なしでインターバルヒープを残します。
• 複数の要素がある場合は、ルートの左端点を返す必要があります。この点はルートから削除されます。
• ルートがインターバルヒープの最後のノードを示している場合、これ以上何もする必要はありません。
• 最後のノードがルートノードでない場合、最後のノードから左の点pを削除します。これにより最後のノードが空になると、最後のノードはヒープの一部ではなくなります。
• 最後のノードから削除されたポイントpは、ルートから開始することにより、埋め込まれた最小ヒープに再挿入されます。
• 下に移動すると、p≤rになるように、現在のpを検査対象のノードの右端点rと交換する必要がある場合があります。再挿入は、通常のヒープへの再挿入に使用されるのと同じ戦略を実装して実行されます。