CSA201 – Applied Data Structures and

Algorithms
Unit 6 Advanced Data Structures

1
What is a Binary Heap?
● A Binary Heap is a Binary Tree with the following properties:

○ It’s a complete tree (All levels are completely filled except possibly the last level
and the last level has all keys as left as possible). This property of Binary Heap
makes them suitable to be stored in an array

○ A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key
at root must be minimum among all keys present in Binary Heap. The same
property must be recursively true for all nodes in a Binary Tree. Max Binary
Heap is similar to MinHeap

2
Types of Binary Heap
● Min heap - the value of each node is less than or equal to the value of both its
children.
● Max heap - it is exactly the opposite of min heap that is the value of each node is
more than or equal to the value of both its children.

80
/ \
70 60
/ \ / \
40 50 30 20
3
Common Operations on Binary Heap
• Creation of Binary Heap,
• Initialize Array
• Set size of Binary Heap to 0

0 1 2 3 4 5 6 7

4
Common Operations on Binary Heap
• Peek of Binary Heap,
• Return array[1] 80
/ \
70 60
/ \ / \
40 50 30 20

80 70 60 40 50 30 20

0 1 2 3 4 5 6 7

5
Common Operations on Binary Heap
• Size of Binary Heap,
• Return number of filled cells
80
/ \
70 60
/ \ / \
40 50 30 20

80 70 60 40 50 30 20

0 1 2 3 4 5 6 7

6
Common Operations on Binary Heap
• Level Order Traversal
80
/ \
70 60
/ \ / \
40 50 30 20

80 70 60 40 50 30 20

0 1 2 3 4 5 6 7

7
Binary Heap – Insert a Node
Algorithm for insertion in Max Heap
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 80

/ \
70 60
/ \ / \
• Heapify is the process of creating a heap data structure
from a binary tree. It is used to create a Min-Heap or a 40 50 30 20
Max-Heap.

Note: For Min Heap, the above algorithm is modified so that parentNode is always smaller than newNode
8
Binary Heap – Insert a Node
• Insert the new element at the end of the tree.

80
/ \
70 60
/ \ / \
40 50 30 20
/
55

9
Binary Heap – Insert a Node
Heapify the tree.
80
Heapify(array, size, i)
set i as largest / \
leftChild = 2i + 1
rightChild = 2i + 2
70 60
/ \ / \
if leftChild > array[largest]
set leftChildIndex as largest 55 50 30 20
if rightChild > array[largest]
set rightChildIndex as largest /
swap array[i] and array[largest] 40

Note: Repeat the heapify until the subtrees are also heapified.
10
Binary Heap – Delete a Node
Algorithm for deletion in Max Heap
If nodeToBeDeleted is the leafNode
remove the node
Else swap nodeToBeDeleted with the lastLeafNode
remove noteToBeDeleted

heapify the array 80

/ \
70 60
/ \ / \
40 50 30 20

For Min Heap, above algorithm is modified so that both childNodes are greater than currentNode.
11
Binary Heap – Delete a Node
1. Select the element to be deleted.

80
/ \
70 60
/ \ / \
40 50 30 20

12
Binary Heap – Delete a Node
2. Swap it with the last element.

80
/ \
20 60
/ \ / \
40 50 30 70

13
Binary Heap – Delete a Node
3. Remove the last element.

80
/ \
20 60
/ \ / \
40 50 30 70

14
Binary Heap – Delete a Node
4. Heapify the tree.

80
/ \
50 60
/ \ /
40 20 30

15
Applications of Binary Heap
1) Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.

2) Priority Queue: Priority queues can be efficiently implemented using Binary Heap
because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn)
time. Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations
perform union also efficiently.

3) Graph Algorithms: The priority queues are especially used in Graph Algorithms like
Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.

4) Many problems can be efficiently solved using Heaps. See following for example.
a) K’th Largest Element in an array.
b) Sort an almost sorted array
c) Merge K Sorted Arrays.
16
What is Hashing?
• Hashing is a method of sorting and indexing data. The idea behind hashing is to allow
large amounts of data to be indexed using keys commonly created by formulas

Hash Function

Apple 18

App 20

Appmillers 22

… Apple App Appmillers

0 1 … 18 19 20 21 22

17
Why Hashing?
• It is time efficient in case of SEARCH Operation

18
Hashing Terminology
Hash function : It is a function that can be used to map of arbitrary size to data of fixed size.
Key : Input data by a user
Hash value : A value that is returned by Hash Function

Hash Table : It is a data structure which implements an associative array abstract data type, a structure
that can map keys to values

Collision : A collision occurs when two different keys to a hash function produce the same output.

Hash Table
Key value

19
Hashing Terminology
Hash function : It is a function that can be used to map of arbitrary size to data of fixed size.
Key : Input data by a user
Hash value : A value that is returned by Hash Function

Hash Table : It is a data structure which implements an associative array abstract data type, a structure
that can map keys to values
Collision : A collision occurs when two different keys to a hash function produce the same output.
Hash Function

ABCD 20

ABCDEF 20 Collision

… ABCD

0 1 … 18 19 20 21 22
20
Hash Functions
Mod function

int mod(int number, int cellNumber) {

return number % cellNumber;
}

mod(400, 24) 16

mod(700, 24) 4

… 700 400

0 1 … 4 … 16 … 22

21
Hash Functions
ASCII function public int modASCII(String word, int cellNumber) {
int total = 0;
for (int i=0; i<word.length(); i++) {
total += word.charAt(i);
System.out.println(total);
}
return total % cellNumber;
}
modASCII(“ABC”, 24) 6

… ABC 400

0 1 … 6 … 16 … 22

22
Hash Functions
Properties of good Hash function
• It distributes hash values uniformly across hash tables

Hash Function

ABCD 20

ABCDEF 20

Collision

… ABCD

0 1 … 18 19 20 21 22

23
Hash Functions
Properties of good Hash function
• It distributes hash values uniformly across hash tables
• It has to use all the input data

ABCD
ABCDEF Hash Function

ABC 18

Collision
… ABCD

0 1 … 18 19 20 21 22

24
Collision Resolution Techniques
1. Direct Chaining : Implements the buckets as linked list. Colliding elements are stored in
this lists 0
Hash Function
1

ABCD 2 2 111 ABCD 222 EFGH 333 IJKLM Null

EFGH 2 3 111 222 333

IJKLM 2 4
IJKLM 7 5

7 444 ABCD 222

444

25
Collision Resolution Techniques
2. Linear probing: It places new key into closest following empty cell
0
Hash Function
1

ABCD 2 2 ABCD

EFGH 2 3 EFGH

IJKLM 2 4 IJKLM

26