Re: Binary heaps


Michal Brzozowski wrote:
> lauren wrote:
> > LOG-HEAP UNION is an operation defined as the union of a binary heap of
> > size N with a binary heap of size log N. Can a binary heap support
> > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in O(log N) time? I'm
> > interested in knowing whether this is (i) impossible (ii) non-trivial,
> > but (maybe) possible (iii) straightforward
> >
> > Thanks,
> > Lauren
>
> If there existed an algorithm that could do LOG-HEAP UNION on two
> normal heaps (by normal I mean without any modifications) as you
> describe it, then it could join any two heaps in linear time to
> their size.
>

Sorry, I didn't prove anything. Joining 2 heaps in linear time
is trivial.

.

Relevant Pages

  • Binary heaps
    ... size N with a binary heap of size log N. Can a binary heap support ... LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... interested in knowing whether this is impossible non-trivial, ... Prev by Date: ...
    (comp.theory)
  • Re: Binary heaps
    ... > size N with a binary heap of size log N. Can a binary heap support ... > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... It is this property that gives Tarjan's algorithm for Minimum Spanning ...
    (comp.theory)
  • Re: Binary heaps
    ... > size N with a binary heap of size log N. Can a binary heap support ... > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... it will join them in linear time. ...
    (comp.theory)