Implementing extract-min in O(1) [duplicate]

This question already has answers here: Closed 12 years ago.

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.

---

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 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)