Implementing extract-min in O(1)

Question

Possible Duplicate:
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

I need to implement a FIFO data structure in which amortized cost of Enqueue, Dequeue and Extract-Min is O(1).

I have thought about using a regular queue which will have O(1) enqueue and dequeue using linked lists and then for Extract-Min I would go through the array to get the min and removie it. the cost for that would be O(n) though and that would not bring the amortized cost to O(1).

Any help or hints would be appreciated.

Hint: what could you add to the data structure to avoid having to traverse the list to find the minimum? — Justin Morgan, Feb 02 '11 at 04:47
I could keep a pointer to the minimum element but them I would have to recompute it at every extract-min. Another way would be to keep a sorted array as an additional list and add to it. Insertion into it would take lg n time but extract-min would then be O(1). This still would not lend to a constant amortized cost for all operations I think — Tom, Feb 02 '11 at 04:50
Its not a duplicate since the question there asks only for get_min() to be implemented while I require and equivalent of pop_min() — Tom, Feb 02 '11 at 05:03
@Tom- What you are being asked to do is impossible if your priority queue relies on comparisons, since it gives you an O(n) comparison-based sorting algorithm (fill in the queue, then keep dequeuing the min). Do you know anything else about your input, such as whether it's integral? Without some extra knowledge about the elements you're not going to be able to solve this. — templatetypedef, Feb 02 '11 at 05:07
The input would be integers. It is not necessary to use an array and I am free to use whichever data structure or create my own. — Tom, Feb 02 '11 at 05:11
@Tom- To the best of my knowledge the fastest-known priority queues on fixed-width integers have O(lg lg n) amortized insertion times, and these structures are pretty terrifying. Trying to beat them might be possible, but you should be aware that you're trying to solve a very hard problem. Is there any particular reason that you want these particular guarantees? Are you sure you're not allowed to have at least some of the operations run in O(lg n) amortized time? — templatetypedef, Feb 02 '11 at 05:35
I am trying to solve a problem out of the CLRS book and they say that we have to implement a dynamic set that supports all these 3 operations in constant amortized cost. The data structure does not have to be a priority queue, it just has to be any dynamic set implementation. And yes, I am pretty sure that the problem asks for constant amortized cost. — Tom, Feb 02 '11 at 05:39
@Tom- What do you mean by "dynamic set?" What specific operations are required? What you've described above is a (slightly modified) priority queue because it has insert and dequeue-min; is this not the case? — templatetypedef, Feb 02 '11 at 06:01
dynamic-set is an abstract data structure that supports a few operations like insert, delete etc. A stack, queue, linked list, priority queue, heap etc are all implementations of a 'dynamic set' since they all support some form of insert and delete operations. The operations I want are atleast ENQUEUE, DEQUEUE and EXTRACT-MIN. THe ENQUEUE and DEQUEUE should work in FIFO style. — Tom, Feb 02 '11 at 06:06
@Tom- Hmmm, that sounds like a standard priority queue that just keeps track of the order in which the elements are added. I'm going to have to give up on this one - if there is a way to get all those operations in amortized O(1), I'd love to see it. — templatetypedef, Feb 02 '11 at 06:08

yasouser · Answer 1 · 2011-02-02T06:16:45.990

You can implement a queue with an extra member which always points to the node with the least value of the queue. The Enqueue() has to be slight modified as shown by the pseudo code below:

void enqueue( data_t val )
{
  back->m_data = val; // back is a pointer to the end of the queue.

  // m_Min should be initialized with a large value.
  if (back->m_data <= m_Min->m_data)
  {
    m_Min = back;
  }
  else // => back->m_data > m_Min->m_data
  {
    swap(back->m_data, m_Min->m_data);
    m_Min = back;
  }
}

The above modification will ensure that enqueue, dequeue and extract_min all run in O(1).

data_t dequeue( )
{
  data_t front_data = front->m_data;

  prev_front = front;
  front = front->next;

  dump prev_front;
  return front_data;
}

So when front reaches m_Min the queue has only one element which will be the least value.

data_t min()
{
  return m_Min->m_data;
}

EDIT: The if-block in enqueue() is modified from my previous version. The enqueue() basically pushes the new value at the end. But swaps with previous node if it is greater than the current min (which is held in the last node of the queue).

For e.g if the input sequence is 5, 3, 7, 1, 4, 6, 8.

1.
front -> 5 <- back
         ^min

2.
front -> 5 3 <- back.
         ^min

front -> 5 3 <- back.
           ^min

3.
front -> 5 3 7 <- back
           ^min

front -> 5 7 3 <- back
             ^min

4.
front -> 5 7 3 1 <- back
             ^min

front -> 5 7 3 1 <- back
               ^min

5.
front -> 5 7 3 1 4 <- back
               ^min

front -> 5 7 3 4 1 <- back
                 ^min

6.
front -> 5 7 3 4 1 6 <- back
                 ^min

front -> 5 7 3 4 6 1 <- back
                   ^min

7.
front -> 5 7 3 4 6 1 8 <- back
                   ^min

front -> 5 7 3 4 6 8 1 <- back
                     ^min

Say you dequeue 3 items, the queue will look like:

front -> 4 6 8 1 <- back
               ^min

So by the time front reached min, the queue will have only one element which will be min.

I don't think this gives you the guarantees you want - in particular, how do you update the min pointer in amortized O(1) after you dequeue the smallest element? — templatetypedef, Feb 02 '11 at 04:59
@templatetypedef: Good catch. The problem comes only if the node with least value is deleted. In that case there will be an overhead of O(n). Without the O(n) overhead, I don't know how to determine the min of a sequence!?!? — yasouser, Feb 02 '11 at 05:25
doesnt this change the sequence and violate FIFO rules. Your insert sequence is 5 3 7 .... but dequeue would give 5 7 3...?? — Tom, Feb 02 '11 at 06:14
Yes it does modify the queue but all (enqueue/dequeue/extract-min) the operations are done in O(1) time. — yasouser, Feb 02 '11 at 06:19

score 0 · Answer 2 · answered Feb 02 '11 at 06:07

0

I would suggest use 2 base data structures together to construct the new one.

First you can use a normal dequeue, which can provide en-Queue and de-Queue in O(1). Then use a helper stack to track the minimal value's pointer. Start from the beginning, when insert the 1st item, just deq.push_back() and stack.push(); then for following items:

Enqueue: push back to dequeue, compare the new item with the top of the stack, if new item is smaller, then push it, otherwise, do nothing. All the operation in O(1)
Dequeue: get the head of the dequeue, compare it with the top of the stack, if they are the same, which means the dequed one is the smallest one, then pop the stack, otherwise, do nothing on the stack. All operations in O(1).
Extract-Min: get the top of the stack, it is the smallest. O(1)

answered Feb 02 '11 at 06:07

Shuo

8,447
4
30
36

I think extract-min needs to *remove* the smallest element, not just hand back its value. Otherwise this is a duplicate of the earlier question. – templatetypedef Feb 02 '11 at 06:14
so say you insert 4, 5, 8, 7. The stack would only have 4 in it and the deque will have 4, 5, 8, 7. How would you handle two consecutive extract-min() ops in O(1) amortized? – Tom Feb 02 '11 at 06:17
yeah, it is not a solution. After I post this, I also realize it is not correct. :( – Shuo Feb 02 '11 at 06:33
I think for Extract-min, it self has no O(1) solution, like a heap sort, it runs in n*log(n). I think there is no O(1) solution.. – Shuo Feb 02 '11 at 06:38

Implementing extract-min in O(1)

2 Answers2

Linked