Given a heap H and a key k, give an algorithm to compute all the entries in H having a key less than or equal to k. For example, given the heap of Figure 9.12a and query k =7, the algorithmshould report the entries with keys 2, 4, 5, 6, and 7 (but not necessarily in this order). Your algorithmshould run in time proportional to the number of entries returned, and should not modify the heap.

Transcribed Image Text:

(2,B) (5.A) (4,C) (15,K) (7,Q) (9,F) (6,Z) (14,E) (11,S) (8,W) (10,1) (12.H) (16,X) (25 J) (20,B) (a)