Array implementation & Construction of Heap

Array implementation & Construction of Heap

• 1.
  Presented By: Arun Brijwasi MCA/25021/18
• 2.
  Heap data structure Arrayimplementation of heap Constructing heap Application of heap
• 3.
  A Heap isa 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 aMin-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.
  A Binary Heapis 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 methoduse to achieve Array representation is Level Order.
• 7.
  Construction of heapcan be: • Max heap construction • Min heap construction Both trees are constructed using the same input and order of arrival.
• 8.
  The algorithm forinserting 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.
  Suppose we havethe following elements in an array: To construct a max heap from tree built from above sequence we need following steps:
• 11.
  After we obtainthe max heap the elements in array will be as follows:
• 12.
  The algorithm forinserting 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.
• 13.
  Consider elements inarray: {10, 8, 9, 7, 6, 5, 4} To construct a max heap from tree built from above sequence we need following steps:
• 15.
  Heaps can beused 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.