Question

Consider an almost-priority-queue data structure, which allows two operations: insert and extract almost min. extract almost min operation outputs either the first minimum or a second minimum item from the current structure (and doesn’t tell you which it outputted). Prove that not both these operations can be done in o(log n) time even if amortization is allowed.

Answer 1

A priority queue is an abstract data type similar to regular queue or stack data structure in which each elements are stored based on priority . In a priority queue, an element with high priority is placed before an element with low priority. In some implementations, if two elements have the same priority, they are placed in the order they are entered.

Proof

Suppose we have N elements and we have to insert these elements in the priority queue. We can use list and can insert elements in O(N) time and can sort them to maintain a priority queue in O(N logN ) time.

But here we don't need sorting to extract the min value.

Only one for()loop is required for insertion and also for extract the minimum value. The code for inserting an element is

void insert_value (int Arr[ ], int val)

{

length = length + 1; Arr[ length ] = -1;

//assuming all the numbers greater than 0 are to be inserted in queue.

increase_val (Arr, length, val1);

}

The time complexity for the code is o(log n);

The code for extracting minimum value is given

int extract_minimum (int Arr[ ])

{

if(length == 0)

{

cout<< “Can’t remove element as queue is empty”;

return -1;

}

int max = Arr[1];

Arr[1] = Arr[length];

length = length -1;

min_heapify(Arr, 1);

return min;

}

The code takes first element as minimum value and places the last element in its position. Then min_heapify function will be called where each value is comapred n-1 times and the time complexity is same as o(log n) even if it is amortized.