Priority Queue, thesarfo

A priority queue is a special queue where each element has an associated priority and is served according to that priority — elements with equal priority are served in queue order. Insertion happens based on arrival; removal happens based on priority.

Assigning Priority

Usually the element’s own value determines its priority — the highest value is the highest priority, though the reverse (lowest value = highest priority) or a custom rule both work too.

Priority Queue vs. Normal Queue

A normal queue is strict FIFO. A priority queue instead removes the highest-priority element first, regardless of arrival order.

Implementation

A priority queue can be built on an array, a linked list, a heap, or a binary search tree — but a heap gives the most efficient implementation.

Operations

Inserting an Element

Insert the new element at the end of the tree.
Heapify the tree.

If there is no node,
  create a newNode.
else (a node is already present)
  insert the newNode at the end (last node from left to right.)

heapify the array

For a min-heap, the rule flips: a parent node is always smaller than the new node.

Deleting an Element

Select the element to delete.
Swap it with the last element.
Remove the last element.
Heapify the tree.

If nodeToBeDeleted is the leafNode
  remove the node
Else swap nodeToBeDeleted with the lastLeafNode
  remove nodeToBeDeleted

heapify the array

For a min-heap, both child nodes must be smaller than the current node instead.

Peeking (Find Max/Min)

Peek returns the max (max-heap) or min (min-heap) element without deleting it — for both, that’s just the root:

return rootNode

Extract-Max / Extract-Min

Extract-Max returns the maximum-value node after removing it from a max-heap; Extract-Min does the same for the minimum value in a min-heap.

Applications

Dijkstra’s algorithm
Implementing a stack
Load balancing and interrupt handling in an OS
Data compression (Huffman coding)