Adaptive heap sort とは

適応ヒープソートは、ヒープソートと同様のソートアルゴリズムですが、ランダム化されたバイナリ検索ツリーを使用して既存の順序に従って入力を構造化します。ランダム化されたバイナリ検索ツリーは、ヒープに配置される候補を選択するために使用されるため、ヒープはすべての要素を追跡する必要はありません。適応ヒープソートは、適応ソートファミリの一部です。
最初の適応型ヒープソートはDijkstra's Smoothsortでした。