Heap

viewed 23029 times and licensed 282 times

Establish the heap property for a given root.

Controller: CodeCogs

Contents

Interface
MaxHeapify
HeapSort
Page Comments

Interface

C++

MaxHeapify

template<class T> voidmaxHeapify(	T*	`vals`
	int	`n`
	int	`root`	)

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$

(2)

$Right(i)=2i+1$

(3)

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

(4)

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.

Note

the root node index starts at 1 rather than 0

Parameters

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

Authors

James Warren (July 2005)

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

HeapSort

template<class T> voidheapSort(	T*	`vals`
	int	`n`	)

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)$

(5)

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 Computing/Sort/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 Computing/Sort/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