Question

Let T be a heap storing 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). For example, given the heap of Figure 5.6 and query key
x = 7, the algorithm should report 4, 5, 6, 7. Note that the keys do not need to be
reported in sorted order. Ideally, your algorithm should run in O(k) time, where
k is the number of keys reported.

Please use psuedocode.

4 6 15 20 16 25 412 1 (11 8

Answer 1

In this problem, root of tree contains the minimum key, so for every single time we have make a comparision between our desired or target value and the root value If the desired key is greater than the key in the root we perform the pop out operation and report that key in the root In order to end the loop, we have to see that either there are no nodes at all or key in the root is greater than the target key Self-restructuring of heap will allow the root value to be minimum for whole time being for any ideal case like, each node is having only right chld in the tree, every opp out operation right child of the root is always the new root of the tree. this gives us a O(1) time We assumed that we have to report k numbers, hence the running time should be O(k) Algorithm print_at max(key z, tree_node n) INPUT Key z, tree_node n(!) OUTPUT The keys of all nodes of the subtree rooted at n with keys at most z. PSEUDOCODE Class Node int data; Node left, right; public Nodeint item) data - item; left= right-null; public class heap_sort_key Node root; boolean isHeap(Node node, min_val, max_val) if (node NULL) return true else (n.get_Key0z) println(n.get keyO) print_at max(z, n.getLeftChild0); print_at max(z, n.getRightChild0): O(K) is the time for this algorithm, the reason for this is there is no node in tree which stores which is a key larger than z that has a descendent storing a key less than z. For example: sample mean (z)-15.11 hypothesized mean (uo) -15 sample size (n) 23 standard deviation(s 0.23 Therefore, t- (z-uo) *sqrt(n)/s-2.293658555