CodeCogs

Establish the heap property for a given root.

You're viewing an older version of this page (#1). View the current version.

Interface

#include <codecogs/computing/sort/heap.h>

using namespace Computing::Sort;

template <class T>void heapSort(T vals[], int n)

Overview

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:

$Left(i)=2i$

(1)

$Right(i)=2i+1$

(2)

$Parent(i)=\frac{i}{2}$

(3)

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

the number of items in the array

root

the root node for the heapify operation

the root node index starts at 1 rather than 0

FUNCTION

heapSort

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:

$T(n) = O(n\ log_2\ n)$

(4)

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 Bucket ). 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 Quick 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 <em> maxHeapify </em> 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 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <codecogs/computing/sort/heap.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]);

  Computing::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

the number of items in the array

Author

James Warren (July 2005)