コンピュータサイエンスにおいて、パイルとは、緩い順序でデータを格納するための抽象データ型です。この用語には2つの異なる用法があり、1つは順序付き両端キューを指し、もう1つは改良ヒープを指します。
順序付き両端キュー
最初のバージョンは、両端キュー (deque) と優先度付きキューの特性を組み合わせたもので、順序付き deque として説明できます。
新しい項目の値が現在の先頭より小さいか等しい場合は、リストの先頭に項目を追加できます。新しい項目の値が現在の末尾より大きいか等しい場合は、リストの末尾に追加できます。先頭と末尾の両方から要素を削除できます。[1]
この種の山は、「UnShuffle ソート」ソート アルゴリズムで使用されます。
ヒープの改善
2番目のバージョンは特許[2] [3]の対象であり、ヒープデータ構造を改善しています。
データ パイル ベースのシステム全体は、次のように一般化できます。
参考文献
- ^ Art S. Kagel、xlinux.nist.gov、「pile」、Dictionary of Algorithms and Data Structures [online]、Paul E. Black 編、National Institute of Standards and Technology、2007 年 9 月 27 日評価。
- ^ 「ヒープスーパーノードを用いたソートのためのデータ構造および方法」、米国特許728147（2000年、2005年発行）
- ^ 「パイプラインヒープソートのためのデータ構造および方法」、米国特許09727534（2000年、2006年発行）
