Heaps
MAP 5010: Data Structures and Algorithms
Semester II, 2025-2026
IIT Jodhpur
Instructor: Dr. Shaily Verma
Revisit FindMin or FindMax
Application: Find the smallest ( or highest priority) item quickly
• Operating system needs to schedule jobs according to priority
instead of FIFO
• Event simulation (bank customers arriving and departing,
ordered according to when the event happened)
• Find student with highest grade, employee with highest salary
etc.
2
Less flexibility -> More speed
Lists
• If sorted: FindMin is O(1) but Insert is O(N)
• If not sorted: Insert is O(1) but FindMin is O(N)
Balanced Binary Search Trees (BSTs)
• Insert is O(log N) and FindMin is O(log N)
Balanced BSTs look good but…
• BSTs are efficient for all Finds, not just FindMin
• We only need FindMin
3
Better than a balanced BST
We can do better than Balanced Binary Search Trees?
– Very limited requirements: Insert, FindMin, DeleteMin.
The goals are:
– FindMin is O(1)
– Insert is O(log N)
– DeleteMin is O(log N)
4
Definition
• Heaps are special kind of binary trees, where the following
properties are satisfied:
• Shape Property:
Heap must be a complete binary tree
•Order Property:
For every node in the heap, the value stored in
that node is greater than or equal to the value
in each of its children (Max Heap Property)
OR
For every node in the heap, the value stored in
that node is less than or equal to the value in
each of its children (Min Heap Property) 5
Examples
6
For a given data set, there can be several ways that satisfy the heap
property
7
Representation of heaps
Since a heap is a complete binary search tree, it can be
represented in an array.
• Root node = A[1]
• Children of A[i] = A[2i], A[2i + 1]
• Parent of A[j] = A[j/2]
• Keep track of current size N (number of nodes)
8
Deletion from heaps
➢An element is always deleted from the root of the heap
➢After deletion, the root node becomes a hole (vacant space)
since the heap is complete binary search tree.
➢We must fill the hole with the last (bottom) element of the heap
➢ Though the heap becomes complete, the order property is
violated as the values that come from the bottom are small.
NEW OBJECTIVE
Given a complete binary tree whose elements satisfy
the heap order property except in the root node, re-
adjust the structure so that it will be heap
9
ReheapifyDownward (for max heaps)
ReheapifyDownward(heap, start, finish)
{
If (heap[start] is not a leaf)
{
index=index of the child with largest value
If(heap[start]<heap[index])
{
Swap(heap[start],heap[index])
ReheapifyDownward(heap, index, finish)
}
}
}
10
Examples
Reheapify
Downward
Swap 33
and 40
11
Delete an element from the Heap
DeleteMax(heap, n, item)
{
item=heap[1];
heap[1]=heap[n];
n=n-1;
ReheapifyDownward(heap, 1, n);
}
Delete 50
Reheapify
Downward
Swap 33
and 40 12
Insertion into heaps
➢An element is always inserted as last (bottom) children of the
heap
➢ Though the heap becomes complete after insertion, the order
property is violated as the values that come from the bottom are
small.
NEW OBJECTIVE
Given a complete binary tree whose elements satisfy
the heap order property except in the last (bottom)
node, re-adjust the structure so that it will be heap
13
ReheapifyUpward (for max heaps)
ReheapifyUpward(heap, start)
{
If (heap[start] is not a root node)
{
If (heap[parent]<heap[start])
{
Swap(heap[parent],heap[start])
ReheapifyUpward(heap, parent)
}
}
}
14
Reheapify
Upward
Swap 35
and 90
Reheapify
Upward
Swap 50
and 90
15
Insert an element into the Heap
Insert(heap, n, item)
{
n=n+1;
heap[n]=item;
ReheapifyUpward(heap,n);
}
16
Examples
Insert 90
Reheapify
Upward
Swap 35
and 90
Reheapify
Upward
Swap 50
and 90
17
Building heaps
Instance: An array
Goal: Build a heap with nodes
18
Building heaps
19