# Heap

Establish the heap property for a given root.

Controller: **CodeCogs**

## Interface

C++

## MaxHeapify

template<class T> voidmaxHeapify( | T* | vals | |

int | n | ||

int | root | ) |

*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.

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

### 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 n the number of items in the array

### 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.