One of the main ways to use the heap data structure is to create a priority queue. As we have seen in Chapter 4, Constructing Stacks and Queues, priority queues are special queues where the FIFO behavior depends on the priority of the element rather than the way items are added to the queue. We have already seen the implementation using Linked list and SPL. Now we are going to explore the priority queue implementation using heap and especially max-heap.
Now we are going to implement the priority queue using MaxHeap. Here, the maximum priority item is removed from the queue first. Our implementation will be similar to our last implementation of MinHeap with a little difference. Instead of starting the root at 1, we want to start it from 0. So, the calculation of the left and right child changes as well. This will help us to understand both approaches of constructing a heap using an array. Here is the implementation for the MaxHeap class:
class MaxHeap {
public $heap;
public $count;
public function __construct(int $size) {
$this->heap = array_fill(0, $size, 0);
$this->count = 0;
}
public function create(array $arr = []) {
if ($arr) {
foreach ($arr as $val) {
$this->insert($val);
}
}
}
public function display() {
echo implode(" ", array_slice($this->heap, 0)) . "
";
}
public function insert(int $i) {
if ($this->count == 0) {
$this->heap[0] = $i;
$this->count = 1;
} else {
$this->heap[$this->count++] = $i;
$this->siftUp();
}
}
public function siftUp() {
$tmpPos = $this->count - 1;
$tmp = intval($tmpPos / 2);
while ($tmpPos > 0 && $this->heap[$tmp] < $this->heap[$tmpPos]) {
$this->swap($tmpPos, $tmp);
$tmpPos = intval($tmpPos / 2);
$tmp = intval($tmpPos / 2);
}
}
public function extractMax() {
$min = $this->heap[0];
$this->heap[0] = $this->heap[$this->count - 1];
$this->heap[$this->count - 1] = 0;
$this->count--;
$this->siftDown(0);
return $min;
}
public function siftDown(int $k) {
$largest= $k;
$left = 2 * $k + 1;
$right = 2 * $k + 2;
if ($left < $this->count
&& $this->heap[$largest] < $this->heap[$left]) {
$largest = $left;
}
if ($right < $this->count
&& $this->heap[$largest] < $this->heap[$right]) {
$largest = $right;
}
if ($largest!= $k) {
$this->swap($k, $largest);
$this->siftDown($largest);
}
}
public function swap(int $a, int $b) {
$temp = $this->heap[$a];
$this->heap[$a] = $this->heap[$b];
$this->heap[$b] = $temp;
}
}
Let's go through our implementation of the MaxHeap class. There are some minor differences in our MaxHeap implementation from our MinHeap implementation in the last section. The first difference is that we have an array of size n for MaxHeap, whereas we had an array of size n+1 for MinHeap. That makes our insert operation for MaxHeap start inserting from index 0, whereas in MinHeap, we started from index 1. The siftUp functionality only sifts a value to the top if the value of the newly inserted item is greater than the immediate parent value. Also, the extractMax method returns the first value of the array at index 0, which is the maximum from the heap. Once we extract the maximum value, we need to get the maximum value from the remaining items and store it at index 0. The siftDown function also operates to check if the left or right child value is bigger than the parent node value and we swap the values to store the maximum value at parent node. We continue to do this recursively to ensure the maximum value is stored in the root at the end of function calls. This MaxHeap implementation can be used as standalone heap implementation if we want. Since we are planning to implement the priority queue using a heap, we are going to add another class to extend the MaxHeap class to show the characteristics of a Priority Queue. Let us explore the following code:
class PriorityQ extends MaxHeap {
public function __construct(int $size) {
parent::__construct($size);
}
public function enqueue(int $val) {
parent::insert($val);
}
public function dequeue() {
return parent::extractMax();
}
}
Here we are just extending the MaxHeap class and adding a wrapper for enqueue and dequeue operations using the insert and extractMax at stealth mode. Let us now run the PriorityQ code with the same numbers we did for MinHeap:
$numbers = [37, 44, 34, 65, 26, 86, 129, 83, 9];
$pq = new PriorityQ(count($numbers));
foreach ($numbers as $number) {
$pq->enqueue($number);
}
echo "Constructed Heap ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
echo "DeQueued: " . $pq->dequeue() . " ";
$pq->display();
As we can see from the preceding code, we are not constructing the heap directly from the array. We are using the priority queue class to enqueue each number in the queue. Also, the dequeue operation will get the top priority item from the queue. If we run this code from the command line, we will have the following output:
Constructed Heap
129 86 44 83 26 34 37 65 9
DeQueued: 129
86 83 44 65 26 34 37 9 0
DeQueued: 86
83 65 44 9 26 34 37 0 0
DeQueued: 83
65 37 44 9 26 34 0 0 0
DeQueued: 65
44 37 34 9 26 0 0 0 0
DeQueued: 44
37 26 34 9 0 0 0 0 0
DeQueued: 37
34 26 9 0 0 0 0 0 0
As we can see from the output, the MaxHeap implementation is helping us to get the maximum value item on each dequeue operation. This is one of the ways of implementing the priority queue. If we want, we can also sort the whole heap at one go and then use the sorted array as the priority queue. For that, we can implement a sorting function that is known as heap sort. It is one of the most efficient and used sorting mechanisms in computer programming. We are now going to explore that in the next section.