3 ms·
Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the n
by mtdewcmu 11y ago
Deletion can't be done efficiently, as pointed out by Timon Gehr:
>> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.
- azakai 11y agoIndeed. If the smallest element is deleted, then we are removing the singleton element of the first heap. We need to find the second-smallest element, which will be in the next heap after it, but it could be any of the leaves. That means we need to traverse O(heapsize) elements. And since we started with the smallest element, this will cascade through each of the heaps, in order to keep them all (but the last) at full size. All together, that's O(N).
- gre 11y agoNever used one, but how about a min-max heap instead? https://en.wikipedia.org/wiki/Min-max_heap https://en.wikipedia.org/wiki/Min-max_heap
- nikic 11y agoThat's true, I got confused with min and max there. gre's suggestion of using a min-max heap (if deletion is required) seems a reasonable workaround for this issue.
- mtdewcmu 11y agoUsing min-max heaps should be workable; indeed, the resulting data structure seems to be a special case of the data structure described in section 3 of [1]. [1] http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/...