# How Priority Queue Is Implemented in Data Structure?

//

Larry Thompson

A priority queue is a data structure that stores a collection of elements, each having a priority assigned to it. The elements with higher priority are dequeued first. In this article, we will explore how a priority queue is implemented in the data structure and understand its working principles.

## Priority Queue Implementation

A common implementation of the priority queue is using a binary heap. A binary heap is a complete binary tree that satisfies the heap property. The heap property states that for every node in the tree, the value of the parent node must be greater (or smaller) than or equal to the values of its children nodes.

There are two types of binary heaps:

• Max Heap: In this type of heap, the value of each node is greater than or equal to the values of its children nodes.
• Min Heap: In this type of heap, the value of each node is smaller than or equal to the values of its children nodes.

### Operations on Priority Queue

A priority queue supports two main operations:

• Enqueue: This operation adds an element to the priority queue while maintaining the order based on their priorities. The element with the highest (or lowest) priority is placed at the front of the queue.
• Dequeue: This operation removes and returns the element with the highest (or lowest) priority from the front of the queue.

### Pseudocode for Enqueue Operation

The enqueue operation consists of adding an element to its correct position based on its priority:

```function enqueue(element)
add element to the end of binary heap
bubbleUp(element) // to maintain the heap property
end function

function bubbleUp(element)
while element has a parent and element is higher (or lower) priority than its parent
swap element with its parent
update element to be its parent
end while
end function
```

### Pseudocode for Dequeue Operation

The dequeue operation consists of removing and returning the element with the highest (or lowest) priority:

```function dequeue()
if binary heap is empty, return an error or null value

swap first and last element in the binary heap
remove the last element from the binary heap

bubbleDown(firstElement) // to maintain the heap property

return removedElement // highest (or lowest) priority element
end function

function bubbleDown(element)
while element has at least one child
select the child with higher (or lower) priority

if child is higher (or lower) priority than element, swap them
update element to be the selected child

continue looping until no more child or element is higher (or lower) priority than its children
end while
end function
```

## Conclusion

A priority queue implemented using a binary heap provides an efficient way to manage elements based on their priorities. The enqueue and dequeue operations ensure that elements are always processed in order of their priorities. Understanding this implementation can help you solve problems that require handling data based on priorities efficiently.