Data structure & algorithms (Heap sorting notes)

Data Structures and Algorithm
(CC-2042)
Lecture 27
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y

, Heap
A Heap is a specialized binary tree
based data structure that satisfies
heap property. The heap property
be one of the following:
1. Max-Heap: The value of a pare
node is always greater than or
equal to the values of its child
nodes.
2. Min-Heap: The value of a pare
node is always less than or eq
the values of its child nodes.



09/06/2025 DS

,Key Characteristics
Key Characteristics
1.Complete Binary Tree:
•A heap is always a complete binary tree, meaning all levels except possibly
the last are fully filled, and the last level is filled from left to right.
2.Heap Property:
•Max-Heap: Parent >= Children
•Min-Heap: Parent <= Children
3.Index Representation:
•A heap can be efficiently represented using an array.
•For a node at index i:
•Parent: floor((i−1)/2)
•Left Child: 2i+1
•Right Child: 2i+2




09/06/2025 DS

, Types of Heaps
MAX-HEAP:THE LARGEST VALUE IS MIN-HEAP:THE SMALLEST VALUE IS
AT THE ROOT. AT THE ROOT.




09/06/2025 DS