We examine on-line heap costruction and on-line permutation routing on trees under the matchign model. Let T be and n-node tree of maximum degree d. By providing on-line algorithms we prove that:(1) For a rooted tree of height h, on-line heap construction can be completed iwthin (2d-1)h routing steps.(2) For an arbitrary tree, on-line permutation routing can be completed within 4dn routing steps. (3) For a complete d-ary tree, on-line permutation routing can be ocmpleted within 2(d-1)n+2dlog sup 2 n routing steps.
展开▼
