## Wednesday, 19 January 2011

### Heap data structure

“Heap as many would assume is not a garbage collected storage or some memory returns by malloc API. Heap is a data structure which looks like a tree with certain properties. Don’t ever confuse it with dynamic or garbage collected memory.”

Introduction

Heap is represented as an array usually and is organized in the form of a tree inside the array.   Heap is something which grows from top to bottom in the form of a binary tree so that, you always get some required value from the root of the tree.There are 2 types of heaps: min heap and max heap. In a min heap, you get the smallest element in the array as the root of the tree. In a max heap, you get the largest element in the array as the root of the tree. These properties are imposed on a heap structure for usage in two kinds of applications: sorting and priority queues.

As we already know, data structures simplify the way algorithm operations are performed. Like how a merge sort got simplified by splitting the array in a tree fashion, heap array is organized in the form of the tree for reducing complexity in processing it,

PARENT(i/2)

LEFT(2i)              RIGHT(2i+1)

Where, i is the index in the array. Usually, when representing heap with an array, we restrict the size of heap so that it is lesser than the total array size. Heap size can increase any time to include some more part of the array.

Note that in merge sort, we split the array with the length of the array at runtime. Here, we use the heap size for calculating PARENT, LEFT, RIGHT values statically and structure it as a tree.

So, if heap size is 6, then the array index gets organized in the form of tree like this.

1                           ---------------- Level 1

/          \

2               3                  --------------- Level 2

/        \        /

4            5    6                      --------------- Level 3