What is a heap data structure?

Heap is a special tree-based non-linear data structure in which the tree is a complete binary tree. A binary tree is said to be complete if all levels are completely filled except possibly the last level and the last level has all elements towards as left as possible. Heaps are of two types:

Max-Heap:
In a Max-Heap the data element present at the root node must be greatest among all the data elements present in the tree.
This property should be recursively true for all sub-trees of that binary tree.

Min-Heap:
In a Min-Heap the data element present at the root node must be the smallest (or minimum) among all the data elements present in the tree.
This property should be recursively true for all sub-trees of that binary tree.

There is an area of memory known as the “heap” from which dynamic memory allocations are made from. There is a set of code known as the “heap manager” which handles memory allocation requests from a program. The heap manager may or may not include a “garbage collector”.

There is also a data structure known as the “binary heap” which is a form of binary tree. It has the property that the value stored at a parent node is always less than that stored in that node’s children (so that the root of the tree always has the minimum value) and that all insertions are made at the same level and a new level of child nodes is not utilized until that level is full.