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.