Data Structure
Presented by
Dr. Md. Matiqul Islam
Associate Professor
Dept. of ICE
University of Rajshahi
Mobile No: +8801716333208
Email: [email protected]
Definitions of heap:
A heap is a data structure that stores a collection
of objects (with keys), and has the following
properties:
Complete Binary tree
Heap Order
The heap sort algorithm has two major
steps :
i. The first major step involves transforming the
complete tree into a heap.
ii. The second major step is to perform the actual sort
by extracting the largest or lowerst element from
the root and transforming the remaining tree into
a heap.
Types of heap
Max Heap
Min Heap
Max Heap Example
19
12 16
1 4 7
19 12 16 1 4 7
ArrayA
Min heap example
1
4 16
7 12 19
1 4 16 7 12 19
ArrayA
1. Max heap :
Max-heap Definition:
is a complete binary tree in which the
value in each internal node is greater
than or equal to the values in the
children of that node.
Max-heap property:
The key of a node is ≥ than the keys of its
children.
Max heap Operation
A heap can be stored as an
array A.
Root of tree is A[1]
Left child of A[i] = A[2i]
Right child of A[i] = A[2i + 1]
Parent of A[i] = A[ i/2 ]
2
5
Build Max-heap
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heapify() Example
Heap-Sort
sorting strategy:
1. Build Max Heap from unordered array;
2. Find maximum elementA[1];
3. Swap elements A[n] andA[1] :
now max element is at the end of the array! .
4. Discard node n from heap
(by decrementing heap-sizevariable).
5. New root may violate max heap property, but its
children are max heaps. Run max_heapify to fix
this.
6. Go to Step 2 unless heap is empty.
HeapSort() Example
20
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
HeapSort() Example
2
1
Heap Sort pseducode
2-Min heap :
Min-heap Definition:
is a complete binary tree in which the value
in each internal node is lower than or equal
to the values in the children of that node.
Min-heap property:
The key of a node is <= than the keys of
its children.
Min heap Operation
A heap can be stored as an array A.
Root of tree is A[0]
Left child of A[i] = A[2i+1]
Right child of A[i] = A[2i + 2]
Parent of A[i] = A[( i/2)-1]
33
Min Heap
Min Heap phase 1
Min Heap phase 1
Min Heap phase 1
Min Heap phase 2
Min Heap phase 2
Min Heap phase 2
Min Heap phase 3
Min Heap phase 3
Min Heap phase 4
Min Heap phase 4
Min Heap phase 5
Min Heap phase 5
Min Heap phase 7
Min Heap final tree
Insertion
Conclusion
Radix Sort
In Computer Science Radix Sort is a non comparative
integer sorting algorithm that sort data with integer keys
by grouping keys by the individual digits which share
same significant position and value.
Radix means the base of a system of numeration.
Lets see the example for Radix sort.
