SplHeap、SplMinHeap、SplMaxHeap、SplPriorityQueueの相違点

Question

ソート順に進む必要があるオブジェクトがたくさんあります。 SplHeap、SplMaxHeap、SplMinHeapの2つのサブクラスが見つかりましたので、私はそれらを実験として使用しようと考えていました。コメントでは、SplPriorityQueuementionedも読んでいます。

しかし、それらを試した後、3つのヒープの違いは何か、そしてヒープとキューの選択方法はちょっと分かりません。ここで

は、すべてのオブジェクトを名前で並べ替えられますことを、「4」クラスですforeachループが正しく内のオブジェクトを一覧表示されます。すなわち、最初から最後まで順番を並べ替え：

class SortedObjectHeap extends SplHeap|SplMinHeap|SplMaxHeap 
{ 
    protected $_property; 
    public function __construct(string $property) 
    { 
     $this->_property = $property; 
    } 
    protected function compare($x, $y) 
    { 
     $x = $x->{$this->_property} ?? null; 
     $y = $y->{$this->_property} ?? null;  
     return strnatcasecmp($x, $y) * -1; 
    } 
} 

$list = new SortedObjectHeap('name'); 
$list->insert($object); 
// ... 

class SortedObjectQueue extends SplPriorityQueue 
{ 
    public function compare($x, $y) 
    { 
     return strnatcasecmp($x, $y) * -1; 
    } 
} 

$list = new SortedObjectQueue(); 
$list->insert($object, $object->name); 
// ... 

質問：

を SortedObjectHeapについては

1. 順番は関係なく、私はSplHeap、SplMaxHeapまたはSplMinHeapを延長するかどうかを、正確に同じでないように見えます。私は、MinとMaxを切り替えるときに順序が逆転すると思っていましたが、それは起こっていないようです...だから、本当にこれら3つのクラスを拡張する違いは何ですか？ドキュメントから

2. 、SplHeapとSplPriorityQueueとの明らかな違いは、キューがinsert方法で余分な$priorityパラメータを取るということです。だから、キューの中では、各インサートで何を並べ替えるべきか、ヒープを使って内部的に「知っている」と言う必要があるようです。違いがあるのでしょうか、それとも他の重要な違いがありますか？私は彼らが多分内部的に動作すると思いますか？どのようにしてこれら2つを選択するのですか？

Answer 1

SplMinHeapとSplMaxHeapが同じ順序を返すことを理由は、あなたがそれらに同様の比較機能の両方を与えているということです。しかし、SplMinHeap::CompareとSplMaxHeap.Compareは異なって定義されています。 value1 < value2場合

SplMinHeap::Compareはvalue1 > value2場合は正の整数を返しSplMaxHeap::Compare、正の整数を返します。

アイテムの「自然な」順序でヒープが必要な場合は、SplMinHeapまたはSplMaxHeapを使用します。あなたが文字列の順序付きリストを作成したいのと同様です。どちらを使用するかは、物事を昇順または降順にするかどうかによって決まります。

各項目に優先度を関連付ける場合は、SplPriorityQueueを使用し、ヒープを優先順位で並べ替える場合は、たとえば、名前はたくさんありますが、システムに挿入された順番に並べ替える必要があります。ジョー、ビリー、メアリー、アリスの順番で表示され、ジョーに優先度1、ビリー優先度2などが与えられます。

しかし、あなたが望むのはソートされたリストですそれらとそれで済む？これは、ヒープを配置してアイテムを一度に1つずつ抽出するよりも高速になります。