“As we move more and more, we see more and more of trees represented in arrays.. Wherever, double recursion is involved, you actually create a tree in an array. But double recursion just emulates array as a tree!!.. What about data structures that has tree kind of structure? Heap is one of this kind!”
We recently studied about the maths behind binary trees specifically and different types of trees. But where would they really use all these trees? One use case is divide-conquer kind of problems where you deploy double recursion to create a tree on the stack. But we have not used tree as a data structure till now. Merge sort, Heap sort and whatever O(nlog n) sort that you can imagine just uses trees to divide and conquer. Then when we plainly represent and use trees: its plainly used on Priority Queues
In Priority Queues, we studied lots of new ADTs and priority queue became nothing but a type of heap data structure. Even heap sort makes use of the heap’s properties and operations. So, its time to study heaps operations. Binary tree as such doesn’t need insertion, deletion plainly until there is a usable structure for it. So we wanted to take Heap as an example here,
- INSERT = add new element to the heap’s bottom
- DELETE = remove max element from the heap
- INCREASE_KEY = change the value to a higher value than existing
- DECREASE_KEY = change the value to lower value than existing
The above functions becomes readable in a tree’s construct only when it is linked with Heap.
We studied max_heapify, heap_insert, increase_key already for heap sort as well as priority queue applications. Here, we gonna reuse the same concepts.
- Max heapify = bubble down, down heap is something which moves an element from top to bottom to satisfy max heap property. We move the element from top to bottom by comparing it with both LEFT and RIGHT
- heap_insert, increase key = bubble up, up heap is something in which we move an element from the bottom to top. We take the element from bottom to top by just comparing with the PARENT
If you note that, both the above routine inserts elements inside the heap and both perform almost equally (with some extra comparisons in max heapify). But both is used for different purposes sometimes.
Adding a new element to the heap
x=15 is the new element we need to insert
Compare with the parent and swap. Continue until the parent is lesser than the child.
Finally, the root gets replaced with the new element added. This is up-bubbling which is carried out by out heap-insert procedure.
Deleting an element
This operation is similar to Heap-extract max routine we saw.
In the above diagram, we remove a max element say 15 from the heap. Since after we remove “15”, we assume the last element “4” as the root, since it would be somewhat least. So, we make “4”, the last node, as the heap’s root node
Now, it violates the heap property!!.. Do max-heapify to down-bubble the element.
- change does both increase, decrease
- max_heapify is reused