let T be a heap sorting n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T). Keys do not need to be reported in sorted order. The algorithm should run in O(k) time where k is the number of keys reported.
p1 point to head, p2 points to tail
while(p1 < p2)
{
if(*p1 < =x&&*p2>=x) {p1++;p2--;}
if(*p1>x&&*p2 < x) {swap(*p1,*p2);p1++;p2--;}
if(*p1 < x&&*p2 < x) {p1++;}
if(*p1>x&&*p2>x) {p2--;}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment