One of the most popular ways to implement a binary heap is using an array. Since heaps are complete binary trees, they can be easily implemented using an array. If we consider the root item to be at index 1, then the child items will be at index 2 and 3. We can represent this as i for the root and 2*i for the left child and 2*i +1 for the right child. Also, we are going to implement the mean heap as our example. So, let us get started with the class structure for the min-heap implementation.

First, we are going to start by creating a class for MinHeap, which will have two properties, one for storing the heap array and another count for the number of elements in the heap at any given moment. Here is the code for the class:

class MinHeap { 

    public $heap; 
    public $count; 

    public function __construct(int $size) { 
        $this->heap = array_fill(0, $size + 1, 0); 
        $this->count = 0; 
    } 
}

If we look at the preceding code, we can see that we have initialized the heap array to have all 0 values from 0 index to $size + 1. Since we are considering putting the root at index 1, we are going to require an array with one extra space. Now we need a way to build a heap from a given array. As we have to satisfy heap property, we have to add one item to the heap and check if the heap property satisfies or not by using the C steps. Here is the code block for creating a heap by inserting one item at a time and also the siftUp process:

public function create(array $arr = []) { 
    if ($arr) { 
        foreach ($arr as $val) { 
            $this->insert($val); 
        } 
    } 
} 

public function insert(int $i) { 
    if ($this->count == 0) { 
        $this->heap[1] = $i; 
        $this->count = 2; 
    } 
    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); 
    } 
} 

First we use the create method to build a heap from an array. For each element in the array, we insert it to the heap using an insert method. In the insert method, we check if the current size of the heap is 0 or not. If the current size is 0, we add the first item to index 1 and setting the next counter at 2. If the heap already has an item, we will store the new item in the last position and increment the counter. We also call the siftUp() method to make sure the newly inserted value satisfies the heap property.

Inside the siftUp method, we consider the last position and its parent position to compare. If the child value is less than the parent one, we swap them. We continue this until we reach the root node at the top. This method ensures that if the inserted value at the end is smallest, it will be sifted up in the tree. But if it is not, the tree will remain as it is. Though we have talked about swapping, we have not seen the implementation yet. Here is the implementation:

public function swap(int $a, int $b) { 
    $tmp = $this->heap[$a]; 
    $this->heap[$a] = $this->heap[$b]; 
    $this->heap[$b] = $tmp; 
}

Since the root element has the minimum value in the heap (we are implementing min-heap). The extract method will return the minimum value of the current heap all the time:

    public function extractMin() { 
        $min = $this->heap[1]; 
        $this->heap[1] = $this->heap[$this->count - 1]; 
        $this->heap[--$this->count] = 0; 
        $this->siftDown(1); 
        return $min; 
    }

The extractMin method returns the first index of the array and replaces it with the last item of the array. After that, it performs the siftDown check for the newly placed root so that it ensures the heap property. Since we are extracting the root value, we are replacing the last index value with 0, which we have used for initializing the heap array. Now we are going to write the siftDown method, which we are calling the extract method:

public function siftDown(int $k) { 
    $smallest = $k; 
    $left = 2 * $k; 
    $right = 2 * $k + 1; 

    if ($left < $this->count &&  
    $this->heap[$smallest] > $this->heap[$left]) { 
        $smallest = $left; 
    } 

    if ($right < $this->count && $this->heap[$smallest] > $this-  
      >heap[$right]) { 
        $smallest = $right; 
    }

    if ($smallest != $k) {
        $this->swap($k, $smallest); 
        $this->siftDown($smallest); 
    }
} 

We consider that the item at index $k is the smallest value. Then we compare the smallest value with the left and right child. If there is smaller value available, we swap the smallest value with the root node and it continues until the tree satisfies the heap property. This function calls itself recursively every time swapping is required. Now we need one more method to display the current heap as a string. For that we can write a small method as follows:

public function display() { 
    echo implode("	", array_slice($this->heap, 1)) . "
"; 
}

If we pull all the pieces together now, we have a solid implementation for min-heap. Let us now run a test to see if our implementation satisfies the min-heap properties. Here is the code we can run to build the heap and also extract the minimum from the heap multiple times:

$numbers = [37, 44, 34, 65, 26, 86, 129, 83, 9]; 
echo "Initial array 
" . implode("	", $numbers) . "
"; 
$heap = new MinHeap(count($numbers)); 
$heap->create($numbers); 
echo "Constructed Heap
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 
echo "Min Extract: " . $heap->extractMin() . "
"; 
$heap->display(); 

If we run this code, the following output will be shown in the terminal:

Initial array
37      44      34      65      26      86      129     83      9
Constructed Heap
9       26      37      34      44      86      129     83      65
Min Extract: 9
26      34      37      65      44      86      129     83      0
Min Extract: 26
34      44      37      65      83      86      129     0       0
Min Extract: 34
37      44      86      65      83      129     0       0       0
Min Extract: 37
44      65      86      129     83      0       0       0       0
Min Extract: 44
65      83      86      129     0       0       0       0       0
Min Extract: 65
83      129     86      0       0       0       0       0       0

As we can see from the preceding output, when we constructed the min-heap, the lowest value of 9 is in the root. Then we extracted the minimum value, we took 9 from the heap. The root was then taken by the next minimum value of 26 and then followed by 34, 37, 44, and 65. Every time we take the minimum out, the heap is reconstructed again for the minimum value. Since we have seen all applicable operations for a heap data structure, we are now going to analyze the complexity for different heap operations.