With things in complete lockdown due to coronavirus situation world over, I was getting bored this weekend. Also I hadn't added any new post here in this blog for quite some time. So thought to write a new post, kind of killing two birds with a stone :P
In today's post I am going to talk about MinHeap.
A min-heap is a binary tree such that - the data contained in each node is less than (or equal to) the data in that node’s children. - the binary tree is complete.
Heaps are useful when we need priority queue kind of structure. Here instead of adding a new item at the end of queue, it could be inserted further up the queue depending on their priority. This helps in a lot of scenario but lesser beings like me could tell you that I used it while solving merge n sorted array task at hacker rank but to see a real real world use case, you may check this Quora answer.
Below is my array based generic implementation of MinHeap in C#. Using array for heap makes it easy to access child/parent nodes, we can do so by using simple formulae:
In today's post I am going to talk about MinHeap.
A min-heap is a binary tree such that - the data contained in each node is less than (or equal to) the data in that node’s children. - the binary tree is complete.
Heaps are useful when we need priority queue kind of structure. Here instead of adding a new item at the end of queue, it could be inserted further up the queue depending on their priority. This helps in a lot of scenario but lesser beings like me could tell you that I used it while solving merge n sorted array task at hacker rank but to see a real real world use case, you may check this Quora answer.
Below is my array based generic implementation of MinHeap in C#. Using array for heap makes it easy to access child/parent nodes, we can do so by using simple formulae:
parentPosition => (currentChildPosition - 1) / 2leftChildPosition => 2 * currentChildPosition +1
rightChildPosition => 2 * currentChildPosition +2
You may like to check this link for more details on heap. Stay Home, Stay Safe!
