Heaps and Priority
Queues
Jollibee L. Lacsama
Instructor
Heap Data Structure
- Is a data structure used to manage information
- Sometimes called ‘binary heaps’
- Nearly complete binary tree
Heap Data Structure
Heap data structure is nearly a complete binary tree that
satisfies the heap property, where any given node is:
• always greater than its child node/s and the key of the root
node is the largest among all other nodes. This property is
also called max heap property.
• always smaller than the child node/s and the key of the root
node is the smallest among all other nodes. This property is
also called min heap property.
Max Heap
• Used for heapsort
Min Heap
• Used for priority
queues
Ex.
node 15
left(3) = 2*3
= 6 (index 6, node 12)
right(3) = 2*3 + 1
= 7 (index 7, node 13)
parent(3) = floor (3/2)
= 1 (index 1, node 21)
Heap Operations
Heapify - is the process of creating a heap data structure
from a binary tree. It is used to create a Min-Heap or a Max-
Heap.
Priority Queue
• special type of queue in which each element is
associated with a priority value. And, elements are
served on the basis of their priority. That is, higher priority
elements are served first.
• However, if elements with the same priority occur, they are
served according to their order in the queue.
Assigning Priority Value
• Generally, the value of the element
itself is considered for assigning the
priority. For example,
• The element with the highest value
is considered the highest priority
element. However, in other cases,
we can assume the element with
the lowest value as the highest
priority element.
• We can also set priorities according
to our needs.
Difference between Priority Queue and
Normal Queue
• In a queue, the first-in-first-out rule is implemented
whereas, in a priority queue, the values are removed on
the basis of priority. The element with the highest
priority is removed first.
Implementation of Priority Queue
• Priority queue can be implemented using an array, a linked
list, a heap data structure, or a binary search tree. Among
these data structures, heap data structure provides an
efficient implementation of priority queues.
Priority Queue Operations
1. Inserting an Element into
the Priority Queue
Inserting an element into a priority
queue (max-heap) is done by the
following steps:
• Insert the new element at the end
of the tree.
Priority Queue Operations
• Heapify the tree.
Priority Queue Operations
2. Deleting an Element
from the Priority Queue
Deleting an element from a
priority queue (max-heap) is done
as follows:
• Select the element to be deleted
Priority Queue Operations
• Swap it with the last
element.
Priority Queue Operations
• Remove the last
element.
Priority Queue Operations
• Heapify the tree.
Priority Queue Operations
3. Peeking from the Priority Queue (Find max/min)
• Peek operation returns the maximum element from Max Heap or
minimum element from Min Heap without deleting the node.
• For both Max heap and Min Heap
Priority Queue Operations
4. Extract-Max/Min from the Priority Queue
• Extract-Max returns the node with maximum value after
removing it from a Max Heap whereas Extract-Min returns
the node with minimum value after removing it from Min
Heap.
THANK YOU!!
