Sample solutions for hw5
- [22.3-1] A binomial tree of order 4.
- [22.3-3] n-1 UNION operations will build a binomial
tree (of hight log n). Repeatedly FINDing the deepest
leaf (say, m>n times) will take the postulated time.
- [22.3-4] Each UNION is charged two units of time: one for
the constant time it takes and another for the use by the FIND
that will traverse the created pointer. Once pointing to the root, the
pointer will be traversed again only when the FIND operation
charged for the cost.
- [22.4-1] The parent pointer p[x] is set when, during
execution of a UNION operation, when the other root's rank is
greater than the rank of x, or it is made larger by
incrementing it. Any subsequent UNION can only increment the rank
of x's parent; a FIND can set p[x] to point to a
node higher up a find path, with a higher rank.
- [22.4-2] log n and log(log n), respectively.
- [22.4-3] UNION operations will build a tree of hight
bounded by log n. Repeatedly FINDing the deepest leaf (say,
m times) will take the postulated time.
- [22-1]
- EXTRACTED= 4 3 2 6 8 1
- An invariant states that the all values of EXTRACTED that
are smaller than i are set correctly and data structure
represents the remaining string of insertions and extractions (without
INSERTions of elements smaller than i and the
EXTRACTions that remove them).
- Representing the sets I as the Union/Find structure, we
can implement line 5 as a FIND and line 6 as a
UNION. For the almost linear complexity of the algorithm, the
(headers K of the) sets should be put in a data structure admitting
constant time deletion, for instance, a doubly liked list.