**Sorting Algorithm Tutorials - Herong's Tutorial Examples** - v6.11, by Herong Yang

Heap Sort - Implementation in PHP

This section provides a tutorial on how to implement the Heap Sort algorithm in PHP.

Heap Sort is a complex and fast sorting algorithm that organizes original collection into a heap which is a binary tree with every node higher that its children in order, then repeatedly takes the root node to the end of the sorted section and rebuilds the heap with remaining notes.

The basic idea of Heap Sort algorithm can be described as these steps:

1. Organize the entire collection of data elements as a binary tree stored in an array indexed from 1 to N, where for any node at index i, its two children, if exist, will be stored at index of 2*i, and 2*i+1.

2. Divide the binary tree into two parts, the top part in which data elements are in their original order, and the bottom part in which data elements are in heap order, where each node is in higher order than its children, if any.

3. Start the bottom part with the second half of the array, which contains only leaf nodes. Of course, it is in heap order, because leaf nodes have no child.

4. Move the last node from the top part to the bottom part, compare its order with its children, and swap its location with its highest order child, if its order is lower than any child. Repeat the comparison and swapping to ensure the bottom part is in heap order again with this new node added.

5. Repeat step 4 until the top part is empty. At this time, the bottom part becomes complete heap tree.

6. Now divided the array into two sections, the left section which contains a complete heap tree, and the right section which contains sorted data elements.

7. Swap the root node with the last node of the heap tree in the left section, and move it to the right section. Since the left section with the new root node may not be a heap tree any more, we need to repeat step 4 and 5 to ensure the left section is in heap order again.

8. Repeat step 7 until the left section is empty.

Here is my PHP implementation of Heap Sort algorithm:

<?php #- Sort_Functions.php #- Copyright (c) 2015 HerongYang.com. All Rights Reserved. #- function heapSort(&$a, $fromIndex, $toIndex) { $n = $toIndex - $fromIndex; for ($i=$n/2; $i>=1; $i--) { downHeap($a,$i,$n,$fromIndex); } for ($i=$n; $i>1; $i--) { $d = $a[$fromIndex]; $a[$fromIndex] = $a[$fromIndex+$i-1]; $a[$fromIndex+$i-1] = $d; downHeap($a,1,$i-1,$fromIndex); } } function downHeap(&$a, $i, $n, $fromIndex) { $d = $a[$fromIndex+$i-1]; while ($i<=$n/2) { $child = 2*$i; if ($child<$n && $a[$fromIndex+$child-1]<$a[$fromIndex+$child]) { $child++; } if ($d>=$a[$fromIndex+$child-1]) break; $a[$fromIndex+$i-1] = $a[$fromIndex+$child-1]; $i = $child; } $a[$fromIndex+$i-1] = $d; } # Functions for other sorting algorithms ... ?>

Note that:

- Data elements are stored in the input array between "fromIndex" and "toIndex", and it is easier to manage a heap array with index from "1" to "n", so I have to do some index conversions like "fromIndex+i-1".

Here are the performance test results of heapSort() function using PHP 5.6.

Array size: 10000 Average sorting time: 46.596 milliseconds Number of tests: 1000 Performance: 4.6596 O(N) microseconds Performance: 0.35066984194897 O(N*Log2(N)) microseconds Performance: 0.00046596 O(N*N) microseconds Array size: 20000 Average sorting time: 100.323 milliseconds Number of tests: 1000 Performance: 5.01615 O(N) microseconds Performance: 0.35108139544997 O(N*Log2(N)) microseconds Performance: 0.0002508075 O(N*N) microseconds Array size: 30000 Average sorting time: 160.008 milliseconds Number of tests: 1000 Performance: 5.3336 O(N) microseconds Performance: 0.35861740022807 O(N*Log2(N)) microseconds Performance: 0.00017778666666667 O(N*N) microseconds

Here is the comparison of mergeSort() performance with other sorting functions.

Array Size 10000 20000 30000 100000 200000 300000 ---------- ----- ----- ----- ------ ------ ------ JDK Arrays.sort 25 66 112 PHP sort() 3 7 13 75 Quicksort 20 42 76 Merge Sort 28 60 93 Heap Sort 47 100 160 Insertion Sort 2213 9484 23329 Selection Sort 3580 14129 33808 Bubble Sort 6847 28427 66524

Table of Contents

Introduction of Sorting Algorithms

Java API for Sorting Algorithms

Insertion Sort Algorithm and Java Implementation

Selection Sort Algorithm and Java Implementation

Bubble Sort Algorithm and Java Implementation

Quicksort Algorithm and Java Implementation

Merge Sort Algorithm and Java Implementation

Heap Sort Algorithm and Java Implementation

Shell Sort Algorithm and Java Implementation

►Sorting Algorithms Implementations in PHP

Sort_Test.php - Sorting Performance Test

Insertion Sort - Implementation in PHP

Selection Sort - Implementation in PHP

Bubble Sort - Implementation in PHP

Quicksort - Implementation in PHP

Merge Sort - Implementation in PHP

►Heap Sort - Implementation in PHP

Shell Sort - Implementation in PHP

Sorting Algorithms Implementations in Perl

Sorting Algorithms Implementations in Python