Question

A max-heap can be used as a max-priority queue, which is an abstract data type having the operations Insert, Maximum, Extract-Max, and Increase-Key.

a. Describe how to implement a FIFO queue with a priority queue, and analyze the time complexity of the implementation (Insert and Delete operations), assuming that a heap is used for the priority queue.

b. Describe how to implement a LIFO queue (i.e. a stack) with a priority queue, and analyze the time complexity of the implementation (Insert (Push) and Delete (Pop) operations), assuming that a heap is used for the priority queue.

Answer 1

The idea of FIFO is first in first out ..we will maintain a MIN_HEAP and heap accepts element having value and it's rank. Rank starts with 1 and gets increased as elements come in. So when pop called for FIFO then rank with minumum element comes out which simulates FIFO because rank starts with 1 and keeps on increasing as elements come in.

Note: Comparison is based on Rank instead of value.

Sample pseudo code for data along with rank which helps in which order data will be popped out.

class Data<T> {
  T x;
  int rank;

  Data(T x, int rank) {
    this.x = x;
    this.rank = rank;
  }
}

Sample pseudo code for FIFO.

class FIFO<T> {
  Queue<Data<T>> queue; // min heap, comparison is based on rank instead of value
  int rank = 1;
  
  void push(T x) {
    queue.push(new Data<T>(x, rank++));
  }

  T pop() {
    return queue.poll();
  }
}

Similarly for LIFO we will maintain MAX_HEAP and rest part will remain same.

Sample pseudo code for LIFO.

class LIFO<T> {
  Queue<Data<T>> queue; // max heap, comparison is based on rank instead of value
  int rank = 1;
  
  void push(T x) {
    queue.push(new Data<T>(x, rank++));
  }

  T pop() {
    return queue.poll();
  }
}