DSA
Presentation
Presented by Suraksha & Anchal
P R E S E N TAT I O N T E M P L AT E
Content
Introduction to Tree
Tree Terminology
Types of Trees
Properties of Tree
Heap
Applications
P R E S E N TAT I O N T E M P L AT E
Tree
Tree is collection of node that are connected by edges and has a
hierarchical relationship between the nodes
Example
P R E S E N TAT I O N T E M P L AT E
Terminology
Successor(Child):
A node that is directly connected to predecessor
Predecessor(Parent):
A parent node is a node which contains at least one node
P R E S E N TAT I O N T E M P L AT E
Ancestor:
Ancestor is a node that is a parent or a parent of parent.
Sibling:
Two node on same place is called sibling
P R E S E N TAT I O N T E M P L AT E
Terminal:
The node which contain no any child node that is called terminal
Non Terminal:
The node which contain child node that is called non
terminal.
.
P R E S E N TAT I O N T E M P L AT E
Types of Trees
1. General tree:
A type which allows for multiple branches and has no limitations
on the number of children
P R E S E N TAT I O N T E M P L AT E
2. Binary tree:
A tree in which every node contains maximum
two child node is called binary node
P R E S E N TAT I O N T E M P L AT E
Types of binary tree
Full binary tree:
A binary tree said to be full binary tree if it’s each node contain
exactly 2-node or 0-node
.
P R E S E N TAT I O N T E M P L AT E
Perfect binary tree: A binary tree in which every
internal node has exactly two children and all leaf
node are at same level
Complete binary tree:
A binary tree said to e complete binary tree
if it’s all the levels are full except the last level
Binary search tree:
A tree said to be binary search tree if it’s all nodes
of left sub part are smaller an right sub part are
the greater from the root node
P R E S E N TAT I O N T E M P L AT E
Introduction to heap
• A heap is a tree based data structure that satisfies the heap property
Heap properties: ordering property of a heap data structure
Shape property: The heap is a complete binary tree,. meaning every level is
filled except the last level
Order property: The parent node is either greater than or less than its child
nodes
P R E S E N TAT I O N T E M P L AT E
Types of heap
Min heap:
the parent node is less than or equal to its child
nodes.
The root node is the minimum element in the
heap
Max heap:
The parent node is greater than or equal to its
child nodes.
the root node is the maximum element in the
heap
P R E S E N TAT I O N T E M P L AT E
Heap tree construction
1. Insert key one by one
.
2. Heapify
Heap construction by insertion way
45 36 54 27 63 72 61 18
P R E S E N TAT I O N T E M P L AT E
Heapify:
The heapify method is a process that reshapes a binary tree into a heap data
structure. This is done by reordering the elements of the tree so that it has the
properties of a min or max heap.
.
P R E S E N TAT I O N T E M P L AT E
Heap sort:
it is a comparison-based sorting technique based on binary heap data
structure. Binary It can be seen as an optimization over selection sort where
we first find the max (or min) element and swap it with the last (or first). We
repeat the same process for the remaining elements.
.
P R E S E N TAT I O N T E M P L AT E
Heap Sort Algorithm
First convert the array into a max heap using heapify, Please note that this
happens in-place. The array elements are re-arranged to follow heap properties.
Then one by one delete the root node of the Max-heap and replace it with the last
node and heapify. Repeat this process while size of heap is greater than 1.
Rearrange array elements so that they form a Max Heap.
Repeat the following steps until the heap contains only one element:
Swap the root element of the heap (which is the largest element in current
heap) with the last element of the heap.
Remove the last element of the heap (which is now in the correct position).
We mainly reduce heap size and do not remove element from the actual
array.
Heapify the remaining elements of the heap.
Finally we get sorted array.
P R E S E N TAT I O N T E M P L AT E
Detailed Working of Heap Sort
Step 1: Treat the Array as a Complete Binary Tree
We first need to visualize the array as a complete binary tree. For an array
of size n, the root is at index 0, the left child of an element at index i is at
2i + 1, and the right child is at 2i + 2.
.
P R E S E N TAT I O N T E M P L AT E
Step 2: Build a Max Heap
P R E S E N TAT I O N T E M P L AT E
STEP 3:
Sort the array by placing largest element at end of unsorted array.
P R E S E N TAT I O N T E M P L AT E
Applications of heap
• Priority queues
THANKYOU
