 # Priority Queue in Python

## Priority Queue in Python

Priority Queues are abstract data structures where each data/value in the queue has a certain priority. For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest.
Priority Queue is an extension of the queue with the following properties.
1) An element with high priority is dequeued before an element with low priority.
2) If two elements have the same priority, they are served according to their order in the queue.
Various applications of Priority queue in Computer Science are:
Job Scheduling algorithms, CPU and Disk Scheduling, managing resources that are shared among different processes, etc.

Key differences between Priority Queue and Queue:
1)In Queue, the oldest element is dequeued first. While, in Priority Queue, element based on highest priority is dequeued.
2)When elements are popped out of a priority queue then result obtained in either sorted in Increasing order or in Decreasing Order. While, when elements are popped from a simple queue, a FIFO order of data is obtained in the result.

Below is simple implementation of priority queue.

 `# A simple implementation of Priority Queue` `# using Queue.` `class` `PriorityQueue(``object``):` `    ``def` `__init__(``self``):` `        ``self``.queue ``=` `[]` ` ` `    ``def` `__str__(``self``):` `        ``return` `' '``.join([``str``(i) ``for` `i ``in` `self``.queue])` ` ` `    ``# for checking if the queue is empty` `    ``def` `isEmpty(``self``):` `        ``return` `len``(``self``.queue) ``=``=` `0` ` ` `    ``# for inserting an element in the queue` `    ``def` `insert(``self``, data):` `        ``self``.queue.append(data)` ` ` `    ``# for popping an element based on Priority` `    ``def` `delete(``self``):` `        ``try``:` `            ``max` `=` `0` `            ``for` `i ``in` `range``(``len``(``self``.queue)):` `                ``if` `self``.queue[i] > ``self``.queue[``max``]:` `                    ``max` `=` `i` `            ``item ``=` `self``.queue[``max``]` `            ``del` `self``.queue[``max``]` `            ``return` `item` `        ``except` `IndexError:` `            ``print``()` `            ``exit()` ` ` `if` `__name__ ``=``=` `'__main__'``:` `    ``myQueue ``=` `PriorityQueue()` `    ``myQueue.insert(``12``)` `    ``myQueue.insert(``1``)` `    ``myQueue.insert(``14``)` `    ``myQueue.insert(``7``)` `    ``print``(myQueue)            ` `    ``while` `not` `myQueue.isEmpty():` `        ``print``(myQueue.delete()) `

Output:

```12 1 14 7
14
12
7
1
```

Note that the time complexity of delete is O(n) in the above code.

better implementation is to use Binary Heap which is typically used to implement priority queue. Note that Python provides heapq in library also.

```By using heap datastructure to implement Priority Queues, Time complexity:
Insert Operation: O(log(n))
Delete Operation: O(log(n))
```

Last Updated on October 28, 2021 by admin

## Pandas dataframe groupby()Pandas dataframe groupby()

Python – Pandas dataframe groupby()   Pandas groupby is used for grouping the data according to the categories and apply a function to the categories. It also helps to aggregate data efficiently. Pandas dataframe.groupby() function is used to split the

## Python – Key index in DictionaryPython – Key index in Dictionary

Python | Key index in Dictionary The concept of dictionary is similar to that of map data structure in C++ language, but with the exception that keys in dictionary has nothing to do with its ordering, i.e it is not

## Creating a Pandas DataFrameCreating a Pandas DataFrame

How to Create a Pandas DataFrame   In the real world, a Pandas DataFrame will be created by loading the datasets from existing storage, storage can be SQL Database, CSV file, and Excel file. Pandas DataFrame can be created from

## Python program to implement Rock Paper Scissor gamePython program to implement Rock Paper Scissor game

Python program to implement Rock Paper Scissor game Python is a multipurpose language and one can do literally anything with it. Python can also be used for game development. Let’s create a simple command line Rock-Paper-Scissor game without using any

## Data Wrangling in PythonData Wrangling in Python

Data Wrangling in Python Data Wrangling is the process of gathering, collecting, and transforming Raw data into another format for better understanding, decision-making, accessing, and analysis in less time. Data Wrangling is also known as Data Munging. Importance Of Data

## How to Get a List of Class Attributes in Python?How to Get a List of Class Attributes in Python?

How to Get a List of Class Attributes in Python? A class is a user-defined blueprint or prototype from which objects are created. Classes provide a means of bundling data and functionality together. Creating a new class creates a new

## Python – os.remove() methodPython – os.remove() method

Python | os.remove() method OS module in Python provides functions for interacting with the operating system. OS comes under Python’s standard utility modules. This module provides a portable way of using operating system dependent functionality. All functions in os module raise OSError in

## Enumerate() in PythonEnumerate() in Python

Enumerate() in Python A lot of times when dealing with iterators, we also get a need to keep a count of iterations. Python eases the programmers’ task by providing a built-in function enumerate() for this task. Enumerate() method adds a