Binary Heap

Binary Heap

In this section we will learn "What is heap?" and "How to construct heap?"

Definition: Heap is a complete binary tree or a almost complete binary tree in which every parent node be either greater or lesser than its child nodes.

Heap can be min heap or max heap.

Types of heap

i)Min heap ii) Max heap

A Max heap is a tree in which value of each node is greater than or equal to the value of its children nodes.

For example

A Min heap is a tree in which value of each node is less than or equal to value of its children nodes.

For example:

Parent being greater or lesser in heap is called parental property. Thus heap has two important properties.

Heap:

i)It should be a complete binary tree

ii)It should satisfy parental property

Before understanding the construction of heap let us learn/revise few basics that are required while constructing heap.

• Level of binary tree: The root of the tree is always at level 0. Any node is always at a level one more than its parent nodes level.

For example:

• Height of the tree: The maximum level is the height of the tree. The height of the tree is also called depth of the tree.

For example:

• Complete binary tree: The complete binary tree is a binary tree in which all the levels of the tree are filled completely except the lowest level nodes which are filled from left if required.

For example:

•. Almost complete binary tree: The almost complete binary tree is a tree in which

 i) Each node has a left child whenever it has a right child. That means there is always a left child, but for a left child there may not be a right child.

ii) The leaf in a tree must be present at height h or h-1. That means all the leaves are on two adjacent levels.

For example:

In Fig. 4.16.5 (a) the given binary tree is satisfying both the properties. That is all the leaves are at either level 2 or level 1 and when right child is present left child is always present.

In Fig. 4.14.5 (b), the given binary tree is not satisfying the first property; that is the right child is present for node 20 but it has no left child. Hence it is not almost complete binary tree.

In Fig. 4.14.5 (c), the given binary tree is not satisfying the second property; that is the leaves are at level 3 and level 1 and not at adjacent levels. Hence it is not almost complete binary tree.