Mergeable heaps with lazy deletion
In class, we have discussed lazy deletion in min-heaps, executable in
constant time and consisting of marking a node (heap element)
"deleted". Since repeated lazy deletions make finding the minimum (of
non-deleted elements) somewhat harder than the normal "eager"
deletion, a good implementation of FIND-MIN would incorporate
"purging" the heap of (lazily) deleted nodes, by constructing a heap
out of the remaining, non-deleted elements.
- Assuming that the (rooted at the root of the heap) subtree of
deleted nodes contains k nodes, describe the algorithm creating
the list of heaps rooted in non-deleted children of the nodes
above. (For instance, if only the root is marked, the list would
consist of its two principal subtrees.)
- Analyze the complexity of the above "listing" algorithm as a
function of k (it better not depend on the size of the heap!)
- Assuming a logarithmic-time heap merging algorithm, analyze the
complexity of FIND-MIN that includes purging lazily deleted nodes.