SplHeap, SplMinHeap, SplMaxHeap 및 SplPriorityQueue의 차이점

Question

정렬 된 순서로 진행해야하는 많은 개체가 있습니다. SplHeap, SplMaxHeap 및 SplMinHeap의 두 하위 클래스가 발견되었으므로 실험으로 사용할 수 있다고 생각했습니다. 의견에서 나는 또한 SplPriorityQueuementioned를 읽었다.

그러나 이들을 테스트 한 후에는 세 개의 힙 간의 차이점과 힙과 큐를 선택하는 방법에 대해 확신 할 수 없습니다.

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); 
// ... 

질문 :

을 여기

는 foreach 루프 개체를 나열합니다 즉, 제대로 순서를 분류에 모두가 처음부터 마지막으로, 이름으로 개체를 정렬 것, "4"클래스입니다 순서가 정확히 동일하게 보이는 SortedObjectHeap를 들어

1. 는 상관없이 나는 SplHeap, SplMaxHeap 또는 SplMinHeap 확장 여부를 지정합니다. Min과 Max 사이를 전환 할 때 순서가 뒤바뀐다고 생각했지만 그렇게되지는 않을 것입니다 ... 그래서이 3 가지 클래스를 확장하는 것의 차이점은 무엇입니까? 워드 프로세서

2. , SplHeap 및 SplPriorityQueue간에 명백한 차이는 큐가 insert 방법 여분 $priority 매개 변수를 사용한다는 것이다. 그래서, 그것은 큐 내부에서 힙을 가지고 "내부적으로"알고있는 동안, 각 인서트에서 어떤 것을 정렬해야하는지 알려주는 것처럼 보입니다. 차이점이 있습니까? 아니면이 둘 사이에 다른 중요한 차이점이 있습니까? 나는 그들이 내부적으로 다르게 작동한다고 가정하니? 어떻게이 두 가지를 선택합니까?

Answer 1

이유가 SplMinHeap 및 SplMaxHeap 같은 순서가 동일한 비교 기능 모두를 제공하고 있다는 것입니다 돌아갑니다. 그러나 SplMinHeap::Compare과 SplMaxHeap.Compare은 다르게 정의됩니다.

SplMinHeap::Comparevalue1 < value2 인 경우 SplMaxHeap::Compare이 양수이면 value1 > value2 인 경우 양의 정수를 반환합니다.

항목의 "자연"순서로 정렬 된 힙을 원할 경우 SplMinHeap 또는 SplMaxHeap을 사용합니다. 정렬 된 문자열 목록을 만들고 싶습니다. 어떤 것을 사용하는가는 오름차순 또는 내림차순으로 물건을 원하는지에 달려 있습니다.

각 항목에 우선 순위를 연결하고 우선 순위에 따라 힙을 정렬하려면 SplPriorityQueue을 사용합니다. 예를 들어, 많은 이름이 있지만 시스템에 삽입 된 순서대로 정렬해야합니다. 그래서 Joe, Billy, Mary, Alice가 순서대로 나타나면 Joe에게 우선 순위 1, Billy 우선 순위 2 등을 부여하십시오.

그러나 원하는 모든 문자열이 정렬 된 목록이라면 그들과 함께 끝내야합니까? 그것은 힙을 채우고 한 번에 하나씩 항목을 추출하는 것보다 빠를 것입니다.