Let S be a set of n points in the plane with distinct integer x- and ycoordinate
ID: 659091 • Letter: L
Question
Let S be a set of n points in the plane with distinct integer x- and ycoordinates.
Let T be a complete binary tree storing the points from S
at its external nodes, such that the points are ordered left-to-right by increasing
x-coordinates. For each node v in T, let S(v) denote the subset of
S consisting of points stored in the subtree rooted at v. For the root r of
T, define top(r) to be the point in S = S(r) with maximum y-coordinate.
For every other node v, define top(r) to be the point in S with highest ycoordinate
in S(v) that is not also the highest y-coordinate in S(u), where
u is the parent of v in T (if such a point exists). Such labeling turns T into
a priority search tree. Describe a linear-time algorithm for turning T into
a priority search tree.
Explanation / Answer
Linear-time algorithm for turning T into a priority search tree
Input: S[1; : : : ; n] of points
h = [log n]; A = n -?? (2h ??- 1);
level = 0;
HeapSort(1; n);
for i = 0 to h -?? 1 do
k = [A/2h-i];
K1 = 2h+1??-i -?? 1;
K2 = 2h-i ??- 1 + A -?? k2h??-i;
K3 = 2h??-i -?? 1;
for j = 1 to k do
l = index in {21 + (j -?? 1)K1,...., 2i + jK1 ??- 1} such that y(S[l]) is maximum or minimum depending on the parity of level ;
swap S[l] and S[2i + j ??- 1] ;
if k < 2i then
l = index in {2i + kK1,...., 2i + kK1 + K2 -?? 1} such that y(S[l]) is maximum or minimum depending on the parity of level ;
swap S[l] and S[2i + k];
m = 2i + kK1 + K2;
for j = 1 to 2i -?? k -?? 1 do
l = index in {m + (j ??- 1)K3,....,m + jK3 -?? 1} such that y(S[l]) is maximum or minimum depending on the parity of level ;
swap S[l] and S[2i + k + j];
HeapSort(2i+1, n);
level = level + 1;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.