Heap Sort - Implementation in Perl

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

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 Perl implementation of Heap Sort algorithm:

#- Sort_Function.pl
#- Copyright (c) HerongYang.com. All Rights Reserved.
#-
sub heapSort {
   my ($a, $fromIndex, $toIndex) = @_;
   my $n = $toIndex - $fromIndex;
   for (my $i=int($n/2); $i>=1; $i--) {
      downHeap($a,$i,$n,$fromIndex);
   }
   for (my $i=$n; $i>1; $i--) {
      my $d = $a->[$fromIndex];
      $a->[$fromIndex] = $a->[$fromIndex+$i-1];
      $a->[$fromIndex+$i-1] = $d;
      downHeap($a,1,$i-1,$fromIndex);
   }
}
sub downHeap {
   my ($a, $i, $n, $fromIndex) = @_;
   my $d = $a->[$fromIndex+$i-1];
   while ($i<=int($n/2)) {
      my $child = 2*$i;
      if ($child<$n && $a->[$fromIndex+$child-1]<$a->[$fromIndex+$child]) {
         $child++;
      }
      last if ($d>=$a->[$fromIndex+$child-1]);
      $a->[$fromIndex+$i-1] = $a->[$fromIndex+$child-1];
      $i = $child;
   }
   $a->[$fromIndex+$i-1] = $d;
}

# Functions for other sorting algorithms ...

#- End
  1;

Note that:

Here are the performance test results of heapSort() function using Perl 5.18

Array size: 10000
Average sorting time: 92.3823974609375 milliseconds
Number of tests: 10
Performance: 9.23823974609375 O(N) microseconds
Performance: 0.695246817677355 O(N*Log2(N)) microseconds
Performance: 0.000923823974609375 O(N*N) microseconds

Array size: 20000
Average sorting time: 200.327661132812 milliseconds
Number of tests: 10
Performance: 10.0163830566406 O(N) microseconds
Performance: 0.701048760680363 O(N*Log2(N)) microseconds
Performance: 0.000500819152832031 O(N*N) microseconds

Array size: 30000
Average sorting time: 314.751000976563 milliseconds
Number of tests: 10
Performance: 10.4917000325521 O(N) microseconds
Performance: 0.705434638826798 O(N*Log2(N)) microseconds
Performance: 0.000349723334418403 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
Perl sort()          11      22      36      171
Quicksort            20      46      75
Merge Sort           48     100     153
Heap Sort            92     200     315
Insertion Sort     4125   16015   37098
Selection Sort     8054   31249   68985
Bubble Sort       19344   78360  177353

Table of Contents

 About This Book

 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

Sorting Algorithms Implementations in Perl

 Sort_Test.pl - Sorting Performance Test

 Insertion Sort - Implementation in Perl

 Selection Sort - Implementation in Perl

 Bubble Sort - Implementation in Perl

 Quicksort - Implementation in Perl

 Merge Sort - Implementation in Perl

Heap Sort - Implementation in Perl

 Shell Sort - Implementation in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB