INFO0902 - Data structures and algorithms

This design choice is left to you. Note, however, that the concept of median cannot be present in the heap implementation; the implementation must be general.

It is a structure whose definition (i.e. the fields it comprises) is not exposed in the .h file. It is an encapsulation mechanism.

As its name suggests, the purpose of the HeapReference is to reference an element of the heap. Since the HeapReference is opaque, you are free to choose what information to store inside (in the Heap.c file).
The only requirement is to be able to access an element in constant time. The content of the HeapReference depends on the representation you chose for the heap (array of pointer-based structure).

Not necessarily. It you opt for the pointer-based representation, you could implement the heap that way. However, it should prove easier to create another structure to represent the heap nodes.
If you go for the array representation, it is discourage to represent the heap as an array of HeapReference.

Your heap cannot have a bounded size. If you decided to implement the heap as an array, it must be extendable. A common way of doing this is to start with an empty array of arbitrary size (though not too large), and to double its length each time it is about to be filled.

Given that you know the value you are looking for, you can do a linear search in the queue.

Given the opacity of HeapReference, you cannot swap elements of a HeapReference array. What you can swap, however, is pointers to HeapReference. We therefore suggest you to use an array of the following structure:

struct heap_queue_item {
    HeapReference* ref; // a single reference to an element of the heap,
                        // obtained by calling referenceArrayAlloc(1)
    size_t heap;        // 0 if the ref points to the max heap, 1 if it points to min heap
};

Such structure allows you to swap the HeapReference (by swapping the HeapReference pointers) when needed.

Again, you can choose to represent your heap as an array or a pointer-based structure. If you choose the array representation, here is how you could implement it.

First, let us consider what information we need to store both in the Heap and HeapReference structures.

In Heap, we obviously need to have an array to represent the heap structure (let us call it heapArray). For the HeapReference, a first idea would be to simply keep an index to the array cell of the element. This however is not a good idea because the elements in heapArray might change positions on heap update (heapAdd, heapReplace), therefore invalidating the references.

We need to go for a different solution. The problem with a single heap array is that element might change position. Therefore, a solution would be to have a second array (let us call it indexes) of which each cell would store the index of a given element in heapArray and we would have to ensure that, in the indexes array, the position of an element does not change. The HeapReference could then simply keep the index of the element in the indexes array (see image below).

Note that to be able to implement the heapAdd and heapReplace operations correctly, you also need to know where is located an element in indexes given its position in the heap.

Finally, in the Heap structure, we need to store the size of the heap (number of elements stored inside of it), the capacity of the heap (total number of elements that can be stored in the current allocated arrays) and whether it is a max- or a min-heap.

If get something like Compression error: 87756716, it relates to the error introduced by the compression as calculated by Eq. (1) of the statement. In other words, the program is working fine.x

In this context, by analytical we expect you to give a formula which can be evaluated in linear time with respect to the length of the interval [p_i, p_{i+1}[, by taking advantage of the error formula.
In contrast, a non-analytical solution could be to

• Search exhaustively the optimal value.
• Devise an iterative procedure which would reduce the error on the optimal solution at each step.

Indeed, there is a missing header defining the size_t type. You can include stddef.
A new version of the code has been uploaded to the website and the submission platforms uses the correct version.

The statement descrbies a greedy approach. You can start from there and improve it. More to the point, the algorithm makes two arbitrary choices that can be improved upon:

• Choosing an interval randomly
• Placing the threshold in the middle

The choices are about where to place the thresholds. If you divide an interval, you are not changing the thresholds. Re-evaluating a choice would be to move a threshold after it had been placed.