269 .Define a heap. Describe the algorithm to insert an element into the heap. 

Ans:
Insertion Sort Algorithm:
Consider an array 'A' with 'N'
elements
1. set A[0]=-infinity [initialize sentinel element]
2. Repeat steps 3 to 5 for K=2,3..,.......N
3. set TEMP=A[K] and PTR=K-1 4 Repeat while TEMP <A[PTR]
(a) set A[PTR+1]=A[PTR] [moves element forward]
(b) set PTR=PTR-1 [End of loop]
5. set A[PTR+1]=TEMP [inserts elements in proper place]
[End of step2 loop]
6. Return
Complexity of insertion sort
Worst case: The worst case occurs when the -array 'A' is in reverse order and the inner
loop must use the max number K-l of comparisons. Hence
F(n)=l+2+........+(n-l)=n(n-l)/2=0(n2)
Average case: In Average case there will be approximately (K-l)/2 comparisons in the
inner loop. Accordingly, for the average case,
F(n)=l/2+2/2+........ ...+(n-l)/2=n(n-l)/4=0(n2)