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
  class Node
  {
  private $_i; 
  
  public function __construct($key)
  {
  $this->_i = $key;
  }
  
  public function getKey()
  {
  return $this->_i;
  }
  }
  
  class Heap
  {
  private $heap_Array;
  private $_current_Size;
  
  public function __construct()
  {
  $heap_Array = array();
  $this->_current_Size = 0;
  }
  
  // Remove item with max key 

 public function remove()
  {
  $root = $this->heap_Array[0];
  // put last element into root
  $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];
  $this->bubbleDown(0); 
  return $root; 
  }
  
  // Shift process
  public function bubbleDown($index)
  {
  $larger_Child = null;
  $top = $this->heap_Array[$index]; // save root
  while ($index < (int)($this->_current_Size/2)) { // not on bottom row
  $leftChild = 2 * $index + 1;
  $rightChild = $leftChild + 1;
  
  // find larger child
  if ($rightChild < $this->_current_Size 
  && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) // right child exists?
  {
  $larger_Child = $rightChild;
  } else {
  $larger_Child = $leftChild;
  }
  
  if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {
  break;
  }
  
  // shift child up
  $this->heap_Array[$index] = $this->heap_Array[$larger_Child]; 
  $index = $larger_Child; // go down
  }
  
  $this->heap_Array[$index] = $top; // root to index
  }
  
  public function insertAt($index, Node $newNode)
  {
  $this->heap_Array[$index] = $newNode;
  }
  
  public function incrementSize()
  {
  $this->_current_Size++;
  }
  
  public function getSize()
  {
  return $this->_current_Size;
  }
  
  public function asArray()
  {
  $arr = array();
  for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
  $arr[] = $this->heap_Array[$j]->getKey();
  }
  
  return $arr;
  }
  }
  
  function heapsort(Heap $Heap)
  { 
  $size = $Heap->getSize();
  // "sift" all nodes, except lowest level as it has no children
  for ($j = (int)($size/2) - 1; $j >= 0; $j--) 
  {
  $Heap->bubbleDown($j);
  }
  // sort the heap
  for ($j = $size-1; $j >= 0; $j--) { 
  $BiggestNode = $Heap->remove();
  // use same nodes array for sorted elements
  $Heap->insertAt($j, $BiggestNode);
  }
  
  return $Heap->asArray(); 
  }
  
  $arr = array(3, 0, 2, 5, -1, 4, 1);
  echo "Original Array : ";
  echo implode(', ',$arr ); 
  $Heap = new Heap();
  foreach ($arr as $key => $val) {
  $Node = new Node($val);
  $Heap->insertAt($key, $Node);
  $Heap->incrementSize();
  }
  $result = heapsort($Heap);
  echo "\nSorted Array : ";
  echo implode(', ',$result)."\n";
  ?>
  

Sample Output:

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

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.