PHP Searching and Sorting Algorithm: Heap sort

PHP Searching and Sorting Algorithm: Exercise-2 with Solution

Write a PHP program to sort a list of elements using Heap sort.

In computer science, heapsort (invented by J. W. J. Williams in 1964) is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it interactively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm, the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.

Animation credits : RolandH

Sample Solution :

PHP Code :

<?php
// Define a Node class for representing elements in the heap
class Node
{
    private $_i; // Key value of the node

    // Constructor to initialize the node with a key value
    public function __construct($key)
    {
        $this->_i = $key;
    }

    // Method to get the key value of the node
    public function getKey()
    {
        return $this->_i;
    }
}

// Define a Heap class for implementing heap data structure
class Heap
{
    private $heap_Array; // Array to store heap elements
    private $_current_Size; // Current size of the heap

    // Constructor to initialize the heap
    public function __construct()
    {
        $this->heap_Array = array(); // Initialize heap array
        $this->_current_Size = 0; // Initialize current size
    }

    // Method to remove item with max key from the heap
    public function remove()
    {
        $root = $this->heap_Array[0]; // Get root element
        $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size]; // Replace root with last element
        $this->bubbleDown(0); // Restore heap property
        return $root; // Return removed element
    }

    // Method to restore heap property by shifting down
    public function bubbleDown($index)
    {
        // Implementation of bubble down process
        $larger_Child = null;
        $top = $this->heap_Array[$index]; // Save root element
        while ($index < (int)($this->_current_Size / 2)) { // Loop until not on bottom row
            $leftChild = 2 * $index + 1;
            $rightChild = $leftChild + 1;

            // Find larger child
            if ($rightChild < $this->_current_Size && $this->heap_Array[$leftChild]->getKey() < $this->heap_Array[$rightChild]->getKey()) {
                $larger_Child = $rightChild;
            } else {
                $larger_Child = $leftChild;
            }

            if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) { // If top key is greater than or equal to larger child's key, break loop
                break;
            }

            // Shift child up
            $this->heap_Array[$index] = $this->heap_Array[$larger_Child];
            $index = $larger_Child; // Move down in the heap
        }
        $this->heap_Array[$index] = $top; // Restore root element
    }

    // Method to insert a node at a specific index in the heap
    public function insertAt($index, Node $newNode)
    {
        $this->heap_Array[$index] = $newNode;
    }

    // Method to increment current size of the heap
    public function incrementSize()
    {
        $this->_current_Size++;
    }

    // Method to get the current size of the heap
    public function getSize()
    {
        return $this->_current_Size;
    }

    // Method to return heap elements as an array
    public function asArray()
    {
        $arr = array();
        for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
            $arr[] = $this->heap_Array[$j]->getKey();
        }
        return $arr;
    }
}

// Function to perform heapsort on a heap
function heapsort(Heap $Heap)
{
    $size = $Heap->getSize(); // Get size of the heap
    // Sift all nodes, except lowest level as it has no children
    for ($j = (int)($size / 2) - 1; $j >= 0; $j--) {
        $Heap->bubbleDown($j); // Bubble down to restore heap property
    }
    // Sort the heap
    for ($j = $size - 1; $j >= 0; $j--) {
        $BiggestNode = $Heap->remove(); // Remove max element from heap
        $Heap->insertAt($j, $BiggestNode); // Insert removed element in the sorted order
    }
    return $Heap->asArray(); // Return sorted array
}

// Input array to be sorted
$arr = array(3, 0, 2, 5, -1, 4, 1);
echo "Original Array : ";
echo implode(', ', $arr);
$Heap = new Heap(); // Create a new heap object
foreach ($arr as $key => $val) {
    $Node = new Node($val); // Create a new node for each element
    $Heap->insertAt($key, $Node); // Insert node into the heap
    $Heap->incrementSize(); // Increment heap size
}
$result = heapsort($Heap); // Perform heapsort on the heap
 echo "\nSorted Array : ";
 echo implode(', ',$result)."\n";
?>
  

Output:

Original Array : 3, 0, 2, 5, -1, 4, 1                               
Sorted Array : -1, 0, 1, 2, 3, 4, 5  

Explanation:

In the exercise above,

• Node Class: This class represents an element in the heap. It has a private property _i to store the key value of the node. The constructor initializes the node with a key value, and the "getKey()" method retrieves the key value of the node.
• Heap Class: This class implements the heap data structure. It has private properties 'heap_Array' to store heap elements and 'currentSize' to keep track of the current size of the heap. The constructor initializes the heap by initializing the heap array and setting the current size to 0. It also contains methods for removing the item with the maximum key from the heap ("remove()"), restoring the heap property by shifting down ("bubbleDown()"), inserting a node at a specific index ("insertAt()"), getting the current size of the heap ("getSize()"), and returning heap elements as an array ("asArray()").
• heapsort Function: This function performs heap sort on a given heap object. It first sifts all nodes in the heap except the lowest level to restore the heap property. Then, it sorts the heap by repeatedly removing the maximum element from the heap and inserting it into the sorted array. Finally, it returns a sorted array.
• Input Array and Sorting: An input array of integers is provided, and each integer is inserted into a heap as a node. The heap is then sorted using the heapsort function, and the sorted array is printed.

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to sort a list of elements using Quick sort.
Next: Write a PHP program to sort a list of elements using Insertion sort.