Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE1729 - Introduction to Programming

2022

Laboratory Assignment 9

Activities 

1.  (Fast Access to the Median.) For some application, we want fast access to the median value of a running list of integers. In order to access the median value of the integers we have been given at any particular time, we will store these integers distributed across two heap data structures. One heap will store roughly half of the values and the other heap will store the remaining integers. We will maintain these heaps in a particular way. One heap will store the lowest integers given in a max-heap (so that the largest integer in the heap is at the root). Note, this is different than the implementation of a heap discussed in lecture. The second heap will store the largest integers given so far in a min-heap (i.e. as discussed in lecture).

Each heap will be stored as a pair consisting of the number of integers in the heap as the car of the pair and the heap in the cdr of the pair. Your integers will be stored in a pair of these heaps. For example, after we

are given the integers 6, 3, 1, 11, and 9, we should have the pair of heaps:

((3  6  (3  (1  ()  ())  ())  ())  2  9  (11  ()  ())  ())

Recall, that when creating a pair of lists, the SCHEME  interpreter will not be able to infer whether the intent was to create a pair of lists or a list of lists.   The SCHEME  interpreter will always choose to dis- play these as a list of lists.  So, the pair of heaps above consists of one heap of three numbers, namely (6  (3  (1  ()  ())  ())  ()) and one heap of two numbers, namely (9  (11  ()  ())  ())

(a)  Define a SCHEME procedure, named (equalize-heaps  heap-pair) which takes a heap pair (in the

format outlined above) and checks to see if they differ in size by more than one integer. If so, then the procedure returns a pair of heaps obtained by removing one element from the larger heap and placing it in the smaller heap until the two heaps are equal or only differ in size by one integer.

(b)  Define a SCHEME procedure, named (add-number  x heap-pair) which adds a new number to our heap pair by inserting the new number, x, into the heap of “smaller” values if it is less than the value at the root of the heap of “smaller” values and into the heap of “larger” values otherwise. Then using equalize-heaps move element(s) between the heaps in the pair until they have roughly the same number of elements.

(c)  Once we have the integers distributed between these two heaps, we can easily access (or compute, if necessary) the effective median of the integers we have stored. If the two heaps have an unequal number of elements stored in them, then the root value of the larger heap is the median value. In the case where both heaps have an equal number of elements, then we must compute the effective median by computing the average of the roots of the two heaps.

In the example above, one heap has three elements, the other has only two. So, the median value is at the root of the heap with three elements, namely 6.

Note, now we have instant access to the median of this collection of numbers. Moreover, we may add numbers to our heap pair at any time and still have instant access to the updated effective median.      Define a SCHEME procedure, named (get-median heap-pair) which returns the effective median of the numbers stored in its single argument, heap-pair.