What is a heap?

Heap is a special data structure based on tree abstract data type, used in many algorithms and data structures. A common example is priority queues, and one of the sorting algorithms is heapsort. In this article we will discuss the properties of the heap, the different types of heaps, and common operations of the heap. We’ll also learn about heap sorting, and we’ll implement heap using SPL.

By definition, a heap is a tree-shaped data structure with a heap feature. If the parent is greater than the children, it is called the maximum heap, and if the parent is less than the children, it is called the minimum heap. Below is an example of the largest heap

If we look at the root node, the value 100 is greater than the two child nodes 19 and 36. For 19, the value is greater than 17 and 3. The same rules apply to other nodes. As we can see, this tree is not completely sorted. But the important fact is that we can always find the maximum or minimum value of the tree, which is very useful in many special cases.

There are many kinds of heap structures, such as binary heap, B heap, Fibonacci heap, ternary heap, tree-based heap, weak heap and so on. Binary heap is one of the most popular heap implementations. A binary heap is a complete binary tree, where all the internal nodes of the tree are fully populated, and the last layer can be fully or partially populated. For binary heaps, we can perform most operations in logarithmic time complexity.

The operation of the heap

The heap is a special tree data structure. We first build the heap based on the given data. Since the heap has strict building rules, we must meet these rules at every step. Here are some of the core operations of the heap.

  • Create a heap

  • Insert the new value

  • Extract minimum or maximum values from the heap

  • Delete a value

  • exchange

Creating a heap from a given set of items or numbers requires that we ensure that the heap rules and binary tree attributes are met. This means that the parent node must be greater or less than the child node. This rule needs to be followed for all nodes in the tree. Again, the tree must be a complete binary tree. When creating the heap, we start with a node and insert a new node into the heap.

When inserting a node, we cannot start with any node. Insert as follows

  • Insert the new node into the bottom of the heap

  • Check the size order of the new node and the parent node and stop if they are in the correct order.

  • If they are not in the correct order, swap them and continue with the previous check. This step together with the previous step is called screening or ascent, etc.

The extract operation (minimum or maximum) is the removal of the root node from the heap. After that, we must do the following to ensure that the remaining nodes still conform to the characteristics of the heap.

  • Move the last node from the heap as the new root
  • The new root node is compared to the child nodes, and if they are in the correct order, stop.
  • If not, swap the root node with the child node (smallest for small root heap and largest for large root heap) and continue with the previous steps. This step, together with the previous step, is called the next heap.

In the heap, an important operation is swap. Now we will implement the binary heap using PHP7.

namespace DataStructure\Heap;

class MaxHeap
{
    public $heap;
    public $count;

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

    public function create(array $arr = [])
    {
        array_map(function($item){
            $this->insert($item);
        }, $arr);
    }

    public function insert(int $data)
    {
        // Insert data operation
        if ($this->count == 0) {
            // Insert the first data
            $this->heap[0] = $data;
            $this->count = 1;
        } else {
            // The newly inserted data is placed at the end of the heap
            $this->heap[$this->count++] = $data;
            // Float up to the right position
            $this->siftUp(); }}public function display(a)
    {
		return implode("", array_slice($this->heap, 0));
    }

    public function siftUp(a)
    {
        // The temporary position of the element to float
        $tempPos = $this->count - 1;    
        // Find the location of the parent node according to the properties of the complete binary tree
        $parentPos = intval($tempPos / 2);

        while ($tempPos > 0 && $this->heap[$parentPos] < $this->heap[$tempPos]) {
            // When it is not the root node and the value of the parent is less than the value of the temporary node, exchange the values of the two nodes
            $this->swap($parentPos, $tempPos);
            // Reset the position of the floating element
            $tempPos = $parentPos;
            // Reset the location of the parent node
            $parentPos = intval($tempPos / 2); }}public function swap(int $a, int $b)
    {
        $temp = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $temp;
    }

    public function extractMax(a)
    {
        // The maximum value is the first value of the heap
        $max = $this->heap[0];
        // Make the last element of the heap the temporary root node
        $this->heap[0] = $this->heap[$this->count - 1];
        // Reset the last node to 0
        $this->heap[--$this->count] = 0;
        // Drop the root node into position
        $this->siftDown(0);

        return $max;
    }

    public function siftDown(int $k)
    {
        // The position of the maximum value
        $largest = $k;
        // The position of the left child
        $left = 2 * $k + 1;
        // The position of the right child
        $right = 2 * $k + 2;


        if ($left < $this->count && $this->heap[$largest] < $this->heap[$left]) {
            // If the left child is greater than the maximum, reset the maximum to the left child
            $largest = $left;
        }

        if ($right < $this->count && $this->heap[$largest] < $this->heap[$right]) {
            // If the right child is greater than the maximum, reset the maximum to the right child
            $largest = $right;
        }


        // If the position of the maximum value is changed
        if($largest ! = $k) {// Switch positions
            $this->swap($largest, $k);
            // Continue sinking until the initial position is unchanged
            $this->siftDown($largest); }}}Copy the code

Complexity analysis

Because different types of heap have different implementations, the various heap implementations have different complexities. But there is one operation on the heap that is O(1) in all implementations, which is to get the maximum or minimum value. I’m going to look at the complexity analysis of the binary heap.

operation Mean complexity Worst complexity
Search O(n) O(n)
Insert O(1) O(log n)
Delete O(log n) O(log n)
Extract O(1) O(1)

Because the binary heap is not completely sorted, the search operation will take more time than the binary search tree.

Heap and priority queue

One of the most common operations is to use the heap as a priority queue. In the PHP implementation stack and THE PHP implementation queue, we’ve seen that a priority queue is a structure for dequeuing based on element weights rather than queuing order. We’ve used linked lists for priority queues and Spl for priority queues, now we use heaps for priority queues.

namespace DataStructure\Heap;

class PriorityQueue extends MaxHeap
{
    public function __construct(int $size)
	{
		parent::__construct($size);
	}

	public function enqueue(int $val)
	{
		parent::insert($val);
	}

	public function dequeue(a)
	{
		return parent::extractMax(); }}Copy the code

Heap sort

In heap sort, we need to build a heap with a given value. Then continuously check the heap values to ensure that the entire heap is sorted at all times. In a normal heap structure, we stop checking every time a new value is inserted into place, but in a heap sort, we keep checking the build heap as soon as the next value arrives. The pseudocode is as follows:

HeapSort(A)
BuildHeap(A)
for i = n-1 to 0
swap(A[0],A[i])
n = n - 1
Heapify(A, 0)

BuildHeap(A)
n = elemens_in(A)
for i = floor(n / 2) to 0
Heapify(A, i)

Heapify(A, i)
left = 2i+1;
right = 2i + 2;
max = i

if (left < n and A[left] > A[i])
max = left
if (right < n and A[right] > A[max])
max = right

if(max ! = i) swap(A[i], A[max]) Heapify(A, max)Copy the code

As you can see from the pseudocode above, the first step in heap sorting is to build a heap. Every time we add a new element to the heap, we call Heapify to satisfy the features of the heap. Once the heap is built and all the elements are checked, let’s use PHP’s implementation of heap sorting. The full code can be viewed here.

function heapSort(&$arr)
{
    $length = count($arr);
    buildHeap($arr);
    $heapSize = $length - 1;
    for ($i = $heapSize; $i >= 0; $i--) {
        list($arr[0], $arr[$heapSize]) = [$arr[$heapSize], $arr[0]];
        $heapSize--;
        heapify(0, $heapSize, $arr); }}function buildHeap(&$arr)
{
    $length = count($arr);
    $heapSize = $length - 1;
    for ($i = ($length / 2); $i >= 0; $i--) { heapify($i, $heapSize, $arr); }}function heapify(int $k, int $heapSize, array &$arr)
{
    $largest = $k;
    $left = 2 * $k + 1;
    $right = 2 * $k + 2;

    if ($left <= $heapSize && $arr[$k] < $arr[$left]) {
        $largest = $left;
    }

    if ($right <= $heapSize && $arr[$largest] < $arr[$right]) {
        $largest = $right;
    }

    if($largest ! = $k) {list($arr[$largest], $arr[$k]) = [$arr[$k], $arr[$largest]]; heapify($largest, $heapSize, $arr); }}Copy the code

Heapsort is O(nlog n) in time and O(1) in space. Heap sort performs better than merge sort.

SplHeap, SplMinHeap, and SplMaxHeap in PHP

Of course, PHP’s handy built-in standard library has helped me implement heaps, which you can use with SplHeap, SplMinHeap, and SplMaxHeap.

More content

PHP basic data structures topic series directory: addresses. PHP syntax is used to summarize basic data structures and algorithms. There are also some basic knowledge that is easily overlooked in our daily PHP development and some practical suggestions on specification, deployment and optimization in modern PHP development, as well as in-depth research on the characteristics of the Javascript language.