AbstractPriorityQueue
in package
AbstractYes
Abstract Priority Queue
It implements a priority queue. Please go to "Data Structures and Algorithms", Aho, Hopcroft, and Ullman, Addison-Wesley, 1983 (corrected 1987 edition), for implementation details.
It provides O(log(N)) time of put/pop operations, where N is a size of queue
Tags
Table of Contents
Properties
- $_heap : array<string|int, mixed>
- Queue heap
Methods
- clear() : void
- Clear queue
- pop() : mixed
- Removes and return least element of the queue
- put() : void
- Add element to the queue
- top() : mixed
- Return least element of the queue
- _less() : bool
- Compare elements
Properties
$_heap
Queue heap
private
array<string|int, mixed>
$_heap
= array()
Heap contains balanced partial ordered binary tree represented in array [0] - top of the tree [1] - first child of [0] [2] - second child of [0] ... [2n + 1] - first child of [n] [2n + 2] - second child of [n]
Methods
clear()
Clear queue
public
clear() : void
pop()
Removes and return least element of the queue
public
pop() : mixed
O(log(N)) time
put()
Add element to the queue
public
put(mixed $element) : void
O(log(N)) time
Parameters
- $element : mixed
top()
Return least element of the queue
public
top() : mixed
Constant time
_less()
Compare elements
protected
abstract _less(mixed $el1, mixed $el2) : bool
Returns true, if $el1 is less than $el2; else otherwise
Parameters
- $el1 : mixed
- $el2 : mixed