PHP Searching and Sorting Algorithm: Heap sort
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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.