Heap Tree

INSERTING AN ELEMENT INTO A HEAP:-

Consider an array H which is a heap and we have a data element say New that we want to insert into the heap. Procedure for inserting the given data element New is as follows. The data element New will be inserted at the end of array H, so that H is still a complete binary tree. After the insertion of element New at the end of heap H, H may not still be a heap.Then this newly inserted element New will rise up to its appropriate position so that tree again becomes a heap. If the newly inserted element New is larger than its parent element then it will exchange its position with its parent element. This procedure will be repeated again and again until New is less than or equal to its parent element or we reach at the root of the tree.

Operations of Heap Data Structure:

Heapify: a process of creating a heap from an array.

• Insertion: process to insert an element in existing heap time complexity O(log N).

• Deletion: deleting the top element of the heap or the highest priority element, and then organizing the heap and returning the element with time complexity O(log N).

• Peek: to check or find the first (or can say the top) element of the heap.

• Types of Heap Data Structure

  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.

  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.

EXAMPLE:

Consider a heap H of size 10 as shown below. We want to insert an element 92 into the heap. Procedure for inserting the data element 92 is illustrated below

A Heap with 10 Nodes

i].inserted the new element 92

As we have inserted the new element 92 at the end of the heap such that it is still a plate binary tree but after inserting 92, the array H is no longer a heap. So, we will compare 92 with its parent element 55. As 55 is smaller than its child 92, we exchange their positions as shown below

iii].False-->replace the value

Now, the newly inserted element 92 will be compared with its new parent element i.e. 72.As its parent element 72 is smaller than it,we will again exchange their positions as shown below:

iv]. CHECK 72>92-->FALSE

v].False-->replace the value

Now, the new element 92 will be compared with its new parent i.e. 85. As its parent 85 is still less than it, we will exchange their positions as shown below:

vi]. CHECK 85>92-->FALSE

vii].False-->replace the value

At this stage, we stop the process of comparisons as we have reached the root node of the tree. At this stage, array H is once again a heap.