HackerRank Queue Quiz-2

A priority queue is implemented by internally building a data structure called a heap. Abstractly, a heap4 is a binary tree in which the value associated with every node is smaller than or equal to the value associated with either child node.

Monotone priority queues are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min-heap) than any item previously extracted. This restriction is met by several practical applications of priority queues.

 

A double ended queue also called deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted or deleted at either end in constant time. It is also known as a head-tail linked list because elements can be added to or removed from either the front (head) or the back (tail) end. However, no element can be added and deleted from the middle

A double ended queue also called deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted or deleted at either end in constant time. It is also known as a head-tail linked list because elements can be added to or removed from either the front (head) or the back (tail) end. However, no element can be added and deleted from the middle

 head-tail linked list is of 2 sub-types:

• An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.


• An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.

An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.

 

:An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.

Applications of Priority Queue:

1) CPU Scheduling

2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc

There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list.

The basic operations on a deque are enqueue and dequeue on either end.