PRIORITY

QUEUES &
APPLICATIONS
WMSU ANDILAB, ELMIDOR, MOJADO

1
Priority Queues
• A priority queue is a data structure that
stores elements with associated priority
values, allowing for efficient access to the
highest (or lowest) priority element.
• Common implementations include heaps
and ordered/unordered arrays.

2
API (Application Programming
Interface)

• An API defines the set of methods

available for interacting with the data
structure.
• Common operations include insert(),
removeMax(), peek(), and isEmpty().

3
4
Priority-Queues Client
• A priority –queues client is a program or
components that interacts with a priority
queue, using it to manage and process
elements based on their priority rather
than their arrival order.

5
Elementary Implementation
• An elementary implementation of a priority
queue typically uses simple data
structures such as arrays or linked lists
without optimizations. These
implementations may be inefficient for
large datasets.

6
Array Representation (Unordered)
• An unordered array stores elements in any
order. Insertions are fast (O(1)), but finding
and removing the maximum (or minimum)
element is slow (O(n)).

7
Finding and Removing Elements:
• Since the array is unordered, to find the maximum or minimum element, you would need
to traverse the entire array to compare all elements.
• This results in a time complexity of O(n) (linear time) for finding or removing the
element.

Example in the Slide:

• The slide shows an array with elements and their corresponding priorities.
• Priorities: [3, 1, 2]
• Elements: [10, 20, 30]
• Indices: [0, 1, 2]
• The array has a Rear pointer at index 2, indicating the last occupied position.

Explanation of Operations:
• Insertion: You add a new element at the rear (next free index) in O(1).
• Finding/Removing Max or Min: You would need to scan all priorities to determine the
highest or lowest, leading to O(n) time.
8
Array Representation
(Ordered)
• An ordered array maintains elements in
sorted order. Insertions are slow (O(n)),
but removing the maximum (or minimum)
element is fast (O(1)).

9
• In an ordered array, elements are maintained in sorted order based on priority
(ascending or descending). In the example, the elements are sorted in
descending order of priority.
• 1. Priorities: The priorities of the elements are [3, 2, 1], which are arranged in
descending order (higher number means higher priority).
• 2. Elements: The corresponding elements are [10, 30, 20].
• 3. Indices: The indices are [0, 1, 2] and represent the positions of the elements in
the array.
• 4. Rear Pointer: The rear pointer is at index 2, meaning the last element was
inserted at that position.
• In the table at the bottom, the priority row shows the priorities of the
elements. The Element row shows the actual values stored in the priority
queue. The Index row shows the positions in the array, starting from 0 to
7 (though only 0 to 2 are currently used). The Rear pointer is indicated
by the arrow above index 2, which means that's the last filled position.

10
Linked-list Representation
• A linked-list representation of a priority
queue can be either ordered or unordered.
It provides dynamic memory allocation but
may be inefficient compared to heap-
based implementations.

11
Heap Definition
• A heap is a complete binary tree that
satisfies the heap property:

• Max-heap: Each parent node is greater

than or equal to its children.

• Min-heap: Each parent node is less than

or equal to its children.
12
Binary Heap Representation

• A binary heap is typically stored in an array, where:

• The root is at index 1.

• The left child of a node at index i is at 2i.

• The right child is at 2i + 1.

• The parent of a node at i is at i/2.

13
Algorithm on Heap

• Operations performed on a heap include

insertion, deletion, reheapification (swim
and sink), and heap sort.

14
Bottom-up Reheapify (Swim) &
Top-down Reheapify (Sink)
• Swim (or percolate up) is used when inserting a
new element into a heap. It compares the element
with its parent and swaps them if necessary,
ensuring the heap property is maintained. Time
complexity: O(log n).

• Sink (or percolate down) is used when removing the

maximum (or minimum) element. It moves the last
element to the root and then swaps it downward
until the heap property is restored. Time complexity:
O(log n).
15
Insert
• The insert operation adds an element to
the heap and restores the heap order
using the swim operation.

16
Remove the Maximum
• In a max-heap, removing the maximum
means removing the root element,
replacing it with the last element, and
restoring heap order using sink.

17
Multiway Heaps
• A multiway heap is a generalization of a
binary heap where each node has more
than two children (e.g., a d-ary heap). This
reduces the height of the tree, making
some operations faster.

18
Array Resizing
• Since heaps are usually implemented
using arrays, array resizing dynamically
increases or decreases the storage
capacity when necessary to optimize
space and performance.

19
Immutability of Keys
• In some applications, keys (priorities) in a
priority queue are immutable
(unchangeable) after insertion to maintain
the correctness of the heap structure.

20
Index Priority Queues
• An index priority queue allows accessing,
modifying, or removing elements based on
an index (position) instead of just priority
order.

21
Index Priority Queues Client
• A client of an index priority queue is an
application or system that uses it to
manage elements efficiently, such as in
graph algorithms (e.g., Dijkstra's shortest
path).

22
Heapsort
• Heap sort is a sorting algorithm that uses a
binary heap to sort elements in O(n log n)
time. It consists of:

• 1. Heap construction (build the heap).

• 2. Repeated removal of the max/min element

and reheapifying.
23
Heap Construction
• Building a heap from an unsorted array
can be done using bottom-up
heapification, achieving an O(n) time
complexity.

24
Sortdown
• Sort down refers to the process of
repeatedly removing the maximum
element from a heap, placing it at the end
of the array, and then restoring heap order.

25
Sink to the Bottom, Then Swim
• A strategy where an element is first sunk
to the bottom of the heap and then swum
up to its correct position. This can be
useful for certain heap reordering
strategies.

26
THANK YOU!

27