Refer to following post for detailed explanation : Find Kth smallest element in unsorted array
Heap is a kind of data structures based on complete tree principle. By definition, a complete binary search tree of N levels has at least 2^N-1 nodes in it.
There two properties heap holds :
1. Structural property : This means every level of heap will be completely full except the last level.
Last level will be filled from left to right order.
2. Heap property : It means parent node will be either greater or smaller than its children nodes.
If we want to find child of a parent node i, it would be 2i or 2i+1.
Watch video on heaps : Insertion and deletion in heaps
Some procedures on heaps
1. Insertion in heap
|Current Max heap|
|Max heap property violated|
After swapping nodes as explained in last step, we should check for if new parent in this case node 14, satisfies heap property. If not, we again swap the largest child and repeat step till we are at root node.. In our case, node 14 satisfies max heap property so we stop there.
|restored heap property|
2. Deletion in heap
Algorithm (This is for max heapify)
- Let i be the index which we doubt that might violate heap property.
- left = 2i, right = 2i+1, largest = a[i]
- Check if left child is with in array limits, if yes, check if it is greater than the a[i].
- If left is greater than a[i], then largest till now is left, largest <– left.
- Check if right is with in array limit, if yes, check if it is greater than largest, then change the largest, largest <– right.
- Swap largest and a[i].
- Now, repeat step 1 to 6 with largest, till we see an element which does not violate heap property.
Let’s take an example:
Now let’s say we delete node 14.
First step is to replace it with last node. In this case 6 will replace 14.
|Last node replacing root|
Node 6 violates max heap property. So, find the largest child of 6, node 12 in this case.Swap node 6 and node 12.
|Heap after swapping|
Again repeat step with node 6 and node 7. Final heap will be like
3. Building a heap from a given array of elements.
- Start from the middle element of the array, let’s say i
- Heapify with given index.
- Decrease index by one. Repeat step 2 till we reach first element.
Idea here that nodes at the lower most level do not move at all. Nodes at one level above lower most, move at most by one level and so on.
If height of heap is h, number of node will be 2^h. So 2^h/2 = 2^h-1 nodes never move.
2^h-2 nodes move by one level and so on.
- Build MAX heap from the given array.
- Swap first and last element of the array. Last element is now at its proper position.
- Decrease the effective size of heap to be heapify.
- Heapify with first element of the array.
- Repeat step 2 , 3 and 4 till we reach the second element of the array.
Complexity of above procedure is O(NlogN).
Permutations and combinations of string
Permutation is arrangement of objects in various positions where order of objects will matter i.e. ab is not same as ba.
Code to print permutations of string
Code to print combinations of string
Reverse words in a string
Code to reverse words of a string
Problem 2 : Rotate an array with a given index as pivot
Complexity of above code is O(N) without using any extra space.
Introduction : Remove particular combination of characters from string.
Same state machine method can be used to count number of words in a given string. Whenever we encounter the separator, we move to OUT state and as soon as we see first character in OUT state we move to IN state till we again see separator.