Interface

#include <codecogs/array/sort/heap_sort.h>

using namespace Array::Sort;

	template<class T> void	maxHeapify (T vals[], int n, int root) Establish the heap property for a given root.
	template<class T> void	heapSort (T vals[], int n) Heap sort an array of values into ascending numerical order.

---

Function Documentation

The function maxHeapify accepts a heap, defined by a pointer to its data and a total node count. It performs the heapify operation on the given root different to the actual root of the heap which resides in position 0 of the data array. A heap is a very important data structure in computing. It can be described as a nearly-complete binary tree. In more simple terms, a heap is a pyramidal data structure which grows downwards from a root node. Each level in the heap has to be complete before the next level begins. Each element in the heap has zero, one or two children. The (max) heap property is that a given node has a value which is greater than or equal to the values held by its children. Heaps are useful because they are very efficiently represented as an array. In the array representation, the following equations are necessary to calculate the indices of the left and right children:

The heapify operation works by assuming that each binary subtree at Left(i) and Right(i) is a heap, but A[i] may be smaller than its children, thus violating the heap property. The value at A[i] is compared with its children and recursively propagated down the heap if necessary until the heap property is restored.

Parameters:

vals	the array of values
n	the number of items in the array
root	the root node for the heapify operation

Note:

the root node index starts at 1 rather than 0

Authors:

James Warren (July 2005)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

Heap sort permutes an array of values to lie in ascending numerical order. The code for heap sort is fairly compact, making it a good all round choice. The complexity of heap sort is:

Heap sort is best applied to very large data sets, of over a million items. The algorithm sorts in-place and therefore does not require the creation of auxiliary arrays (such as Array/Sort/bucketSort ). The algorithm is also non-recursive, so can never cause a stack overflow in the case of large data arrays. Heap sort is beaten by Array/Sort/quick_Sort in terms of speed, however, with large data sets the recursive nature of quick sort can become a limiting factor.

Heap sort works by firstly transforming the array of values into a max-heap using the maxHeapify function. The maximum values are then read out from the top of the heap one at a time, shrinking the heap by one iteratively. A index moves from the end of the array backwards. Here the maximum values are stored, creating the ascending sorted list.

Example:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#include <codecogs/array/sort/heap_sort.h>
 
int main()
{
  double vals[25];
  int n=25;
 
  for (int i=0; i<n; i++) vals[i]=((double) n*rand())/RAND_MAX;
 
  printf("\nArray to be sorted:\n");
  for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
 
  Array::Sort::heapSort(vals, n);
 
  printf("\nSorted array:\n");
  for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
  printf("\n");
  return 0;
}

Output:

Array to be sorted:
 23   6   6  13  11  10  13   4   9   4
 17  14   7   5  16   7  21   7  17  17
 23   6  16   9  18
Sorted array:
  4   4   5   6   6   6   7   7   7   9
  9  10  11  13  13  14  16  16  17  17
  17  18  21  23  23

Parameters:

vals	the array of values to be sorted
n	the number of items in the array

Authors:

James Warren (July 2005)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.