Category Archives: Algorithms
Understanding of Heap data structure is very important as it is part of many other data structures like priority queue and algorithms like priority queues, Dijkstra’s.
Let’s understand Heap data structure first. Heap is a simple tree based data structure with a unique property that root node is always larger or smaller than its children.
In the current heap we can see parent element is always higher than child nodes, hence it is called max heap. Similarly in case the parent is smaller than children, it will be min heap. Also the heap shown above is binary heap as each parent node has only two child nodes.
Let’s talk about efficiency of the heap data structure in terms of Inserting and deleting the nodes.
Insert a Key: To insert a new node, new element is added to next possible leaf node. It is then compared to its parent node and moved up if larger.
1. Insert node at next leaf
2. While element is less than parent
Swap child and parent
Insert operation in a heap data structure is order of log N, where N is number of nodes available.
Delete Node: Deletion always occur at the root node. Last leaf node is moved to root and then moved down till it is greater than children.
1. Node =root
2. While node <any child
Swap node and largest child
Delete operation in a heap data structure is order of log N, where N is number of nodes available.
Insertion sorting, as the name suggest, is about inserting the elements of an unsorted array to their correct position one by one. To make it clearer, lets say we have an unsorted array. We take another array, which is empty initially and then we will keep adding numbers one by one into this array at their correct positions.
Say the original array A is
5, 3, 7, 2, 6
Now we take first element and add to zeroth position of a new array B, so B is now containing 5
next we pick 3 from original array and add to first position of B, it becomes 3, 5
After step 3 B is, 3, 5, 7 and then 2, 3, 5, 7 and finally 2, 3, 5, 6, 7
We have taken 2 arrays just to make things clear, the sorting functionality can be achieved with 1 array only. Instead of taking an additional array, we will think of original array as 2 sub-parts, at any given time first N-x elements are sorted and remaining x are not sorted.
Again taking the original array A
5, 3, 7, 2, 6
Step 1: 5 (sorted till here), 3, 7, 2, 6
Step 2: 3, 5 (sorted till here), 7, 2, 6
Step 3: 3, 5, 7 (S), 2, 6
Step 4: 2, 3, 5, 7, (S) 6
Step 5: 2, 3, 5, 6, 7 – Final
If there are N elements in array, at Nth point, we know we have N-x sorted and x unsorted. We pick up next element (N-x+1)st, and need to insert it into proper position in for N-x+1 elements. So in worst case we need to make N-x comparisons (in best case 1 comparison). The process has to be repeated N times for N elements.
So in worst case we have comparisons like
1+2+3+.. +N= N*(N-1)/2 which is quadratic i.e. N*N.
In best case (sorted array) we have 1+1+1+.. N times comparison which is order of N (linear).
We generally take worst case complexity so we will say Insertion sort has complexity of N^2.