We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Actually, the answer to this question fills a cavity in my explanation. When I say that a heap can be thought to be a binary tree, I implicitly think of it is a complete binary tree. Therefore, we should also preserve the completeness.
Keeping that in mind, it is clear that we need to swap the deleted element inside the tree with the last leaf child, which is purposely the last element of our array. By this, we are sure that the completeness is preserved. It is heap[last] in my code. Let's call it lastChild.
So what about lastChild now residing inside the tree after deletion? We know that it must be greater than its children now, if there are any. That was why that element was the last member of the heap. So this very situation breaks the heap property. To restore, it must go downwards through the complete binary tree. That is where sink() becomes handy.
Can't we use a non-complete binary tree? Most probably, but then we must keep track of deleted indicies in the array. Moreover, the array will consume much more space than it actually needs. I have not coded but we can also shrink the size of the array if the last becomes a predefined portion (maybe 1/4) of array capacity. No matter what, I will try to code that implementation and share if it succeeds.
QHEAP1
You are viewing a single comment's thread. Return to all comments →
Actually, the answer to this question fills a cavity in my explanation. When I say that a heap can be thought to be a binary tree, I implicitly think of it is a complete binary tree. Therefore, we should also preserve the completeness.
Keeping that in mind, it is clear that we need to swap the deleted element inside the tree with the last leaf child, which is purposely the last element of our array. By this, we are sure that the completeness is preserved. It is
heap[last]
in my code. Let's call itlastChild
.So what about
lastChild
now residing inside the tree after deletion? We know that it must be greater than its children now, if there are any. That was why that element was the last member of the heap. So this very situation breaks the heap property. To restore, it must go downwards through the complete binary tree. That is wheresink()
becomes handy.Can't we use a non-complete binary tree? Most probably, but then we must keep track of deleted indicies in the array. Moreover, the array will consume much more space than it actually needs. I have not coded but we can also shrink the size of the array if the
last
becomes a predefined portion (maybe 1/4) of array capacity. No matter what, I will try to code that implementation and share if it succeeds.