In our computers, we want to use data in an easy and efficient way. For that, we use data structures to store data. All these data structures can be divided on the basis of how they store data.
WHAT IS COMPLETE BST?
A complete binary tree is the one in which all levels are filled except the last and in the last level all the nodes are to the left with no gaps in-between and all parents have two children. If we represent complete binary trees in an array, we would not get any gaps between the indexes. The height of the complete binary tree will be minimum always which is log2N because unless one level is filled we will not go to the next level. Here are a few examples of complete binary trees.
WHAT IS HEAP?
Heap is a tree-based data structure in which all the nodes of the tree are in a specific order. Heap is always a complete binary tree. While converting a Heap to an array we must keep in mind the following:
- The root element of the heap should be at index 0 in the array.
- For the node at index i:
- At index (i-1)/2 is the parent node
- At index (2*i)+1 is the left child node
- At index (2*i)+2 is the right child node
This method of achieving array representation is called Level Order. Hence, it satisfies the Ordering Property.
Heaps are of the following two types:
MAX HEAP
In this type of heap, the value of the parent node is always larger than the child nodes. Hence, the root node is occupied by the largest value in the whole heap. To understand how to convert a heap into a max heap, let’s see the example below.
In this, we can clearly see that 4 is on the root who’s child 7 and 8 both are greater than it. Hence, we swap 4 with 8 which is the greatest of all three. We perform the similar action in the 2nd step. Now we check children of 4 and find that it is still smaller than both. So once again we swap it with the largest one that is 6 in this case. Finally, 4 has reached the leaf node and no more operations can be performed.
Complexity for max heap in O(logN).
MIN HEAP
In this type of heap, the value of the parent will always be less than both of the children. Hence, the least value in the whole heap is at the root of the heap. To understand this better let's see this quick example.
In the diagram, we can see that the number 4 in the root is greater than one of its child 1. Hence we swap it with 1. In the second step, once again the number 4 is larger than its child 2. So we once again swap it with 2. Finally, the result we get is a min-heap in which the smallest number is at the root.
The complexity of a min-heap is O(N).
HEAP OPERATIONS
Some necessary operations which will be performed on the heap are given below.
- HEAPIFY
It is a process of creating a min or max heap from a binary tree.
- Let the input array be and build an entire binary tree from the array.
2. Start from the first index of the non-leaf node whose index is given by n/2 -1 and set current element i as the largest element.
3. If the left child is greater than the current element(i.e. element at i th index), set the left child as largest. If the right child is greater than the element in largest, set the right child as largest.
4. Swap largest with current element and the repeat steps until the subtrees are also heapified.
Create Max Heap using Heapify:
MaxHeap(array, size)
loop from the first index of non-leaf node down to zero
call heapify- DELETE
Deleting an element is very easy. All we have to do is swap the element to be deleted to the last leaf element and delete that last leaf node. Then heapify the tree.
- PEAK
Peek operation returns the maximum element from Max Heap or minimum element from Min Heap without deleting the node.
- Extract
Extract-Max returns the node with maximum value after removing it from a Max Heap whereas Extract-Min returns the node with minimum after removing it from Min Heap.
HEAP SORT ALGORITHM
There are various kinds of sorting methods used in sorting different kinds of data structures. One of the popular and efficient sorting methods in computer science is Heap Sort which requires the knowledge of arrays and trees/heap. Now let us see how heap sort works and what steps we have to use.
- From the elements of the given array, we have to make a max heap. We can start heapifying each sub-tree from the bottom up and end up with a max-heap after the function is applied to all the elements including the root element.
- Remove the root element and put it at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place.
- Reduce the size of the heap by 1.
- Heapify the root element again so that we have the highest element at root.
- Keep repeating this process again and again until all the items of the list are sorted in the array successfully.
For the image given below, we can see that these steps have been followed successfully for the numbers to be sorted.
HEAP SORT COMPLEXITY
The time complexity of heap sort for worst, average, and worst case is the same that is O(nlog n).
HEAP SORT APPLICATION
- Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(nlog n) upper bound on Heapsort's running time and constant o(1) upper bound on its auxiliary storage.
- Heap can be efficiently used if we want to extract the smallest (or largest) from the list of items without the overhead of keeping the remaining items in the sorted order. For e.g Priority Queues.
Even though Heap Sort has O(nlog n) complexity for even worst case, it doesn't have any more applications compared to other sorting algorithms (like quick, merge, bubble sort). However, it's one of the most interesting and obviously efficient algorithms.
