PriorityQueue
in package
Uses a binary tree stored in an array to implement a heap.
Tags
Table of Contents
Properties
Methods
- extract() : T|null
- Deletes and returns the data at the top of the queue if the priority is less than the priority given.
- insert() : void
- Inserts the key into the queue with the given priority or updates the priority if the key already exists in the queue.
- isEmpty() : bool
- peekData() : T|null
- Returns the data at top of the heap or null if empty. Time complexity: O(1).
- peekPriority() : int|null
- Returns the priority at top of the heap or null if empty. Time complexity: O(1).
- remove() : void
- Removes the given key from the queue.
- heapifyDown() : void
- heapifyUp() : void
- removeAndRebuild() : void
- swap() : void
Properties
$data
private
array<int, T, priority: int}>
$data
= []
$pointers
private
array<string|int, mixed>
$pointers
= []
Methods
extract()
Deletes and returns the data at the top of the queue if the priority is less than the priority given.
public
extract([int $priority = PHP_INT_MAX ]) : T|null
Time complexity: O(log(n)).
Parameters
- $priority : int = PHP_INT_MAX
-
Extract data with a priority less than the given priority.
Return values
T|nullinsert()
Inserts the key into the queue with the given priority or updates the priority if the key already exists in the queue.
public
insert(T $key, int $priority) : void
Time complexity: O(log(n)).
Parameters
- $key : T
- $priority : int
isEmpty()
public
isEmpty() : bool
Return values
boolpeekData()
Returns the data at top of the heap or null if empty. Time complexity: O(1).
public
peekData() : T|null
Return values
T|nullpeekPriority()
Returns the priority at top of the heap or null if empty. Time complexity: O(1).
public
peekPriority() : int|null
Return values
int|nullremove()
Removes the given key from the queue.
public
remove(T $key) : void
Time complexity: O(log(n)).
Parameters
- $key : T
heapifyDown()
private
heapifyDown(int $node) : void
Parameters
- $node : int
-
Rebuild the data array from the given node downward.
heapifyUp()
private
heapifyUp(int $node) : void
Parameters
- $node : int
-
Rebuild the data array from the given node upward.
removeAndRebuild()
private
removeAndRebuild(int $node) : void
Parameters
- $node : int
-
Remove the given node and then rebuild the data array.
swap()
private
swap(int $left, int $right) : void
Parameters
- $left : int
- $right : int