Question 1: Consider we implement a priority queue as a heap. Suppose the queue has thousands of elements. Consider further that we have four different priorities (1-4, highest to lowest). The heap typically has 5% of priority 1 elements, 10% priority 2 elements, 15% priority 3 elements, and 70% of priority 4 elements. The probability of the recently arriving element at priority i, P(i) is P(1) = 0.05, P(2) = 0.10, P(3) = 0.15 and P(4) = 0.7.
a) Evaluate the average complexity of an enqueue operation.
b) Determine the average complexity of the dequeue (remove) operation.
Question 2: Let's analyze the Heap dequeue/enqueue operations with different assumptions. Suppose that the elements already in the queue were put into a sequence with the head element at the front at the lowest priority elements toward the end. Then consider that any new element to be enqueued is equally likely to be placed anywhere into that sequence. You can suppose that the heap contains n = 2k-1 elements for simplicity.
a) Evaluate the average complexity of an enqueue operation.
b) Determine the average complexity of the dequeue (remove) operation.
Question 3: We considered building a balanced (or full) BST from a sorted array. Suppose that the array has n = 2k-1 elements in sorted order. We will insert the array middle element first (as the root), then insert the middle element of the left half, then the middle element of the right half, and so on recursively. Since the array has n elements, the actual work at each level is the insert into the BST. Define the model for the total number of comparisons to insert all the elements into the BST.