Analysis Design Of Algorithm (ADA) | Heap and Heap Sort Concept

📌Highlights: Hi friends ! In this post I am going to discuss about the concept of  Heap and Heap sort algorithm such as what is heap ?, Type of heap, Array representation of heap and examples.

Heap is a special type of binary tree. It is a complete binary tree and must satisfy heap property. 

Heap property says that the key value of parent node must be (greater than or equal to) or (Lesser than or equal to) the value of child node.

Now for understanding heap tree let we discuss about binary tree first.

Binary tree is a tree in which every parent have not more than two children. Binary tree are classified into following:

1. Full Binary Tree :

A binary tree in which every node has either 0 or 2 children. A single node is also a binary tree. 

Example:

2. Complete Binary Tree :

A binary tree in which all the levels are completely filled except possibly the last level and for the last level either completely filled or must be filled from left to right as possible. In complete binary tree it is not necessary that all parent have two children. 

Example:

3. Perfect Binary tree :

A binary tree in which all the internal nodes have 2 children and all leaf nodes are at the same level.

Example:

Note: All full binary tree can be complete binary tree but all complete binary tree need not necessary be a full binary tree.

Type Of Heap :

Heap is classified into following:

1. Max Heap

2. Min Heap

In Max Heap largest element must be parent node. In other words every parent have maximum value then their children. The property of max heap is

a[parent(i)] >= a[i]

In Min Heap smallest element must be parent node. In other words every parent have minimum value then their children. The property of min heap is 

a[parent(i)] <= a[i]

We use array for storing heap elements. Fro this array we can find following things such as:

👉 If we want to find root element of tree than use a[1]. It will display root element.

👉 If we want to find left child of a[i] than we use a[2i]. It will display left element of a[i].

👉 If we want to find right child of a[i] than we use a[2i+1]. It will display right element of a[i].

👉 If we want to find the parent of a[i] than we use a[i/2]. It will display parent of a[i].

👉 Note Heap size [a] <= length [a]

👉The element in the sub array are called levels. For finding the number of levels of any heap tree we use [((n/2)+1) - n]. It will display the number of levels of heap tree.

👉We use  2^k  (where k is level) for finding the number of elements in any level k.

Example:

let we understand by the help of tree.

👉 1. Find the root element.

a[1] = 50

👉 2. Find left child of a[2] 

a[ 2i ] = a[ 2 * 2 ] = a[4] = 20

👉 3. Find right child of a [5]

a[2i + 1] = a[ (2 * 5) + 1] = a[11] = 6

👉 4. Find how many labels in tree. (where n=10)

[ ((n/2) + 1) - n ] = [((10/2)+1) - 11] = [(5+1)-10] = 4 (i.e 0 to 3)

👉 5. Find how many number of elements in label 3.(where k=3)

2^k = 2³ = 8 ([ but here in 3rd level we have only 4 elements because it is not a full binary tree]

👉 Note : In Heap sort we consider only max heap and min heap will be ignored because we always sort element in increasing order. If we sort in decreasing order than we only consider min heap.

📌Now this end of this post. In this I covered the concept of  Heap and Heap sort algorithm such as what is heap ?, Type of heap, Array representation of heap and examples for better explanation.I hope it is useful for you we will meet in next post till continue reading...