SplPriorityQueue::compare — Compare priorities in order to place elements correctly in the heap while sifting up
SplPriorityQueue::count — Counts the number of elements in the queue
SplPriorityQueue::current — Return current node pointed by the iterator
SplPriorityQueue::extract — Extracts a node from top of the heap and sift up
SplPriorityQueue::getExtractFlags — Get the flags of extraction
SplPriorityQueue::insert — Inserts an element in the queue by sifting it up
SplPriorityQueue::isCorrupted — Tells if the priority queue is in a corrupted state
SplPriorityQueue::isEmpty — Checks whether the queue is empty
SplPriorityQueue::key — Return current node index
SplPriorityQueue::next — Move to the next node
SplPriorityQueue::recoverFromCorruption — Recover from the corrupted state and allow further actions on the queue
SplPriorityQueue::rewind — Rewind iterator back to the start (no-op)
SplPriorityQueue::setExtractFlags — Sets the mode of extraction
SplPriorityQueue::top — Peeks at the node from the top of the queue
SplPriorityQueue::valid — Check whether the queue contains more nodes

Improve This Page

Learn How To Improve This Page • Submit a Pull Request • Report a Bug

＋add a note

User Contributed Notes 4 notes

down

rajatn at rediff dot co dot in ¶

14 years ago

quick implementation of SPL Priority Queue:



<?php



class PQtest extends SplPriorityQueue

{

    public function compare($priority1, $priority2)

    {

        if ($priority1 === $priority2) return 0;

        return $priority1 < $priority2 ? -1 : 1;

    }

}



$objPQ = new PQtest();



$objPQ->insert('A',3);

$objPQ->insert('B',6);

$objPQ->insert('C',1);

$objPQ->insert('D',2);



echo "COUNT->".$objPQ->count()."<BR>";



//mode of extraction

$objPQ->setExtractFlags(PQtest::EXTR_BOTH);



//Go to TOP

$objPQ->top();



while($objPQ->valid()){

    print_r($objPQ->current());

    echo "<BR>";

    $objPQ->next();

}



?>



output:



COUNT->4

Array ( [data] => B [priority] => 6 ) 

Array ( [data] => A [priority] => 3 ) 

Array ( [data] => D [priority] => 2 ) 

Array ( [data] => C [priority] => 1 )

down

doublecompile at gmail dot com ¶

9 years ago

I've used the SplPriorityQueue to determine an HTTP client's preferred MIME types.

<?php
$queue = new \SplPriorityQueue();
foreach (preg_split('#,\s*#', $_SERVER['HTTP_ACCEPT']) as $accept) {
    $split = preg_split('#;\s*q=#', $accept, 2);
    $queue->insert($split[0], isset($split[1]) ? (float)$split[1] : 1.0);
}
foreach ($queue as $mime) {
    echo $mime, PHP_EOL;
}
?>

My browser sends:
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8

And this script outputs:
text/html
application/xhtml+xml
application/xml
*/*

A better example:
Accept: text/html, application/xml,text/css;q=0.4,text/plain; q=0.9, application/json;q=0.8

And this script outputs:
text/html
application/xml
text/plain
application/json
text/css

down

Hayley Watson ¶

10 years ago

For a heap-based priority queue to be at its most effective, the "priority" should be something that can take on a wide range of values (lengths, timestamps, populations). It optimises the tasks of searching the queue for the appropriate place to insert an item (and inserting it); and removing the first item in the list.

Items may potentially be inserted into the queue wherever two adjacent items have different priorities. The heap structure is an efficient way of indexing such insertion points when there are many of them distributed throughout the list.

If you have a sharply-limited enumeration of possible priority values, then there are very few insertion possible insertion points - one for each priority value. In that situation, one can make the insertion points explicit (and thus eliminate the need to maintain a heap indexing them) by implementing your priority queue as a list of simple queues from which you draw successive items from the highest-priority nonempty queue.

down

lsroudi at gmail dot com ¶

10 years ago

<?php

/**
 * Description of PriorityQueue
 *
 * (c) lsroudi http://lsroudi.com/ <lsroudi@gmail.com>
 * 
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */
interface PriorityLoggerInterface {

    public function insert($value, $priority);
}

class PriorityLogger extends SplPriorityQueue implements PriorityLoggerInterface {
    
}

class Logger {

    const ERROR = 3;
    const NOTICE = 1;
    const WARNING = 2;

    private $priorityLogger;

    public function __construct(PriorityLoggerInterface $priorityLogger)
    {
        $this->priorityLogger = $priorityLogger;
    }

    public function addMessage($value, $priority)
    {
        $this->priorityLogger->insert($value, $priority);
    }

    public function getPriorityLogger()
    {
        return $this->priorityLogger;
    }

}

$priorityLogger = new PriorityLogger();

$logger = new Logger($priorityLogger);
$logger->addMessage('Message with notice type', Logger::NOTICE);
$logger->addMessage('Message with warning type', Logger::WARNING);
$logger->addMessage('Message with error type', Logger::ERROR);

$priorityLoggerQueue = $logger->getPriorityLogger();

foreach ($priorityLoggerQueue as $queue){
    print $queue . PHP_EOL;
}

//Résultat
//Message with error type
//Message with warning type
//Message with notice type
?>

＋add a note