Array implementation & Construction of Heap

This is an PPT of Data Structure. It include the following topic "Array implementation & Construction of Heap".

1. BIRLA INSTITUTE OF TECHNOLOGY,MESRA RANCHI JAIPUR CAMPUS Presentation on: “Array implementation and construction of heap ” Presented By: Arun Brijwasi MCA/25021/18

2. contents Heap data structure Array implementation of heap Constructing heap Application of heap

3. Heap data structure A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types: 1. Max-Heap : In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

4. 2. Min-Heap : In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree

5. Array implementation of heap A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as array. The representation is done as: The root element will be at Arr [0]. Indexes of other nodes : Arr [(i-1)/2] Returns the parent node Arr [(2* i )+1] Returns the left child node Arr [(2* i )+2] Returns the right child node

6. The traversal method use to achieve Array representation is Level Order.

7. Construction of heap Construction of heap can be: Max heap construction Min heap construction Both trees are constructed using the same input and order of arrival.

8. Max Heap Construction Algorithm The algorithm for inserting one element in max heap is as follows: Step 1 − Create a new node at the end of heap. Step 2 − Assign new value to the node. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds.

9. Example Suppose we have the following elements in an array: To construct a max heap from tree built from above sequence we need following steps:

10. After we obtain the max heap the elements in array will be as follows:

11. Min heap construction algorithm The algorithm for inserting one element in max heap is as follows: Step 1 − Create a new node at the end of heap. Step 2 − Assign new value to the node. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is more than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds.

12. Example Consider elements in array: {10, 8, 9, 7, 6, 5, 4} To construct a max heap from tree built from above sequence we need following steps:

13. Application of heap Heaps can be used in sorting the elements in a specific order in efficient time. It is known as Heap sort. Priority queues can be efficiently implemented using Binary Heap.