The dequeue operation takes linear time (O(n)) because we need to search through the queue in order to find the item with maximum priority. In an unordered linked list, we can insert the item at the end of the queue in constant time. The complexity of enqueue operation is O(n) and dequeue and peek operation is O(1). In the ordered linked list, we can insert item so that the items are sorted and the maximum item is always at the end (pointed by head or tail). The linked can be ordered or unordered just like the array. search the maximum item in the array and replace it with removes the item with the maximum priority insert an item at the rear of the queue The following C program implements the priority queue using an unordered array. It is obvious that the complexity of dequeue and peek operation is O(n). The dequeue operation is illustrated in figure 2. Once we remove this item, we need to move all the items after it one step to the left. Since the queue is not ordered, we need to search through the queue for the item with maximum priority. The complexity of this operation is O(1). While inserting, we do not maintain the order. We insert the item at the end of the queue. Printf( "%s\n", "ERROR: Queue is empty") queue so that the queue is always ordered insert an item at the appropriate position of the The C program below implements the enqueue and dequeue operation using an ordered array. Since the item with the highest priority is always in the last position, the dequeue and peek operation takes a constant time. Since we must scan through the queue in order to find the appropriate position to insert the new item, the worst-case complexity of this operation is O(n). We can insert it at the end of the queue. The item with priority 7 is inserted between the items with priorities 6 and 8. The insertion operation is illustrated in figure 1. The item is inserted in such a way that the array remains ordered i.e. ImplementationĪ priority queue can be implemented using data structures like arrays, linked lists, or heaps. The complexity of these operation depends upon the underlying data structure being used. Peek: Peek operation reads the item with the highest priority.DeQueue: DeQueue operation removes the item with the highest priority from the queue.The item can be inserted at the end of the queue or at the front of the queue or at the middle. EnQueue: EnQueue operation inserts an item into the queue.Just like the regular queue, priority queue as an abstract data type has following operations. The disabled people have the highest priority followed by elderly people and the normal person has the lowest priority. The real world example of a priority queue would be a line in a bank where there is a special privilege for disabled and old people. If the two items have same priorities, the order of removal is undefined and it depends upon the implementation. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. Therefore, the FIFO pattern is no longer valid.Įvery item in the priority queue is associated with a priority. However, in a priority queue, an item with the highest priority comes out first. Regular queue follows a First In First Out (FIFO) order to insert and remove an item.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |