Basic Concept Of Heap
Hello everyone, so today we're going to talk about something called Heap. So according to wikipedia, heap is a specialized-data structure that satisfies the heap property. It is also said that it implements the concept of priority queue in data structure.
Pretty confusing, eh.
To make things easier to comprehend, I came up with my own definition of heap if you dont mind. To me, heap is like a compilation of sorted array that is unifies in the end as root node. Here is an illustration of heap:
Pretty confusing, eh.
To make things easier to comprehend, I came up with my own definition of heap if you dont mind. To me, heap is like a compilation of sorted array that is unifies in the end as root node. Here is an illustration of heap:
(max-heap)
Based on my explanation, I see that heap as 5 array of data :
1. array of [100,19,17,2]
2. array of [100,19,17,7]
3. array of [100,19,3]
4. array of [100,36,25]
5. array of [100,36,1]
See how it all starts with 100? That's what I meant by "they unifies in the end [it is indeed an end if you look from bottom to top]". But, there's more to it though, if you look closely, all of those arrays are sorted in descending order from the top to bottom. This is what it meant by implementation of priority queue :
"Each array is sorted in a certain way based on their value that we call as priority".
In this case, every array is sorted in top-down descending order as it is max-heap
This might led you thinking: if there's max, there must be min heap.
You're right about it. There are three kinds of heap, which is: Max-Heap, Min-Heap, and Min-Max Heap.
As you seen above, for Max-heap, the topmost node of the tree has the maximum value, and decreases gradually as it reaches the bottom.
As for Min-heap, it is the opposite of Max-heap. The topmost node has the minimum value, and increases gradually as it reaches the bottom.
As for Min-max heap, it gets a little tricky as its an combination of both min and max heap. (Assuming that root node equals the height 1, its first gen of descendant is 2, second gen is 3, and so-on) In min-max tree:
1.For every Odd height, it has the min-heap property [meaning it contains the minimum value and gets bigger as it progresses downward]
2. For every Even height, it has the max-heap property [meaning it contains the maximum value and gets smaller as it progress downward]
min-max heap
Insertion
Insertion in heap is the same as any binary tree, where it creates new node whenever is necessary. What differs it from normal BST, is however, after every insertion, it is followed by a Bubble-Up Operation. Bubble-Up Operation is a repositioning action that makes sure the tree still follows the 'Heap-property' after a new data is inserted.
How it works: It's an recursive method. In every iteration, the child node compares its value to its parent's value. If it's larger, or smaller [it depends on the type of heap], then perform a swap operation, and keeps on moving upward until the condition no longer meets.
Deletion
In heap, normally it's the root node that gets deleted as it applies the concept of queue. But matters not, the following algorithm will still work. So, after a node is deleted [we call it node A], we replace node A value, with the last child node we perform insertion on. Then we perform another repositioning-operation like what we did in Insertion. However, deletion uses the exact opposite operation from Insertion, it's called Sink-Down Operation.
How it works: It's an recursive method. In every iteration, we (node A) compare our value, with our child node. The child that has the maximum or minimum value [again, it depends on the type of heap] get swapped with the value of the current node (node A). After that, proceed downward towards the child node that we performs the swap on and repeat until the last node.
Source :
Comments
Post a Comment