Please read about the binary heaps before using them in a priority queue. Using binary heaps, we can make all the operations faster (in logarithmic time). In above implementations using arrays and linked lists, one operation always takes linear time i.e. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |