Heap, Types of Heap, Insertion and Deletion

This pdf will explain what is heap, its type, insertion and deletion in heap and Heap sort

1. Heap
A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly
used to implement priority queues, efficient sorting algorithms, and memory management.
Heap Properties:
1.Complete Binary Tree:
•A heap is always a complete binary tree, meaning all levels are completely filled
except possibly the last level, which is filled from left to right.
2.Heap Order Property:
•Max Heap: The value of each parent node is greater than or equal to the values of
its children.
•Min Heap: The value of each parent node is less than or equal to the values of its
children.
Types of Heaps
(A) Max Heap
•The root node contains the largest value in the heap.
•Application:- Priority Queue.
(B) Min Heap
•The root node contains the smallest value in the heap.
•Applications: Used in Dijkstra’s Algorithm, Prim’s Algorithm, and Priority Queues.
Prepared by:- Kale J. N.

2. Prepared by:- Kale J. N.

3. Heap Operations
(A) Insertion in Heap
Heapify-up (also known as bubble-up) is an operation used to restore the heap property
after an insertion in a binary heap.
When you insert a new element into a binary heap, it is initially placed at the last position of the
heap (i.e., at the end of the heap array). After this insertion, the heap may violate the heap property,
especially in a Max Heap, where the parent node should always be greater than or equal to its child
nodes.
To fix this violation, we perform the heapify-up operation, which involves comparing the inserted
element with its parent and moving it up the tree if it is out of order (in the case of a Max Heap, if
the inserted element is larger than its parent). The process is repeated until the heap property is
satisfied or the element becomes the root.
Steps for Heapify-up:
1.Compare the inserted element (at the last position) with its parent.
2.If the element is greater than its parent (in a Max Heap), swap the two elements.
3.Repeat the process for the element's new position (the parent node), comparing and
swapping until the heap property is restored, or the element becomes the root.
Prepared by:- Kale J. N.

4. Prepared by:- Kale J. N.

5. Deletion from Heap (Removing the Root Element)
1.Replace the root node with the last node in the heap.
2.Remove the last node.
3.Compare the root node with its largest (Max Heap) or smallest (Min Heap) child and
swap if necessary (heapify-down).
4.Repeat step 3 until the heap property is restored.
Prepared by:- Kale J. N.

6. Prepared by:- Kale J. N.

7. Heap Sort:-
Heap can be used as a sorting technique, known as Heap Sort.
Heap Sort works in two main phases:
1.Build a Max Heap: Convert the input array into a Max Heap (a complete binary tree where
the parent node is always greater than or equal to its children). This ensures that the largest
element is at the root of the heap.
2.Extract Maximum & Rebuild Heap:
•Swap the root (largest element) with the last element in the heap.
•Reduce the heap size by 1 and heapify the root to maintain the max heap property.
•Repeat until all elements are sorted.
Heap Sort Steps in Detail
To begin, convert the array into a Max Heap by applying the heapify process. This rearranges the
elements in place so that the array satisfies the Max Heap property — where each parent node is
greater than or equal to its children.
Once the array is in Max Heap form, repeatedly perform the following steps until only one element
remains in the heap:
1.Swap the first element of the heap (which is the largest) with the last element in the current
heap range.
2.Consider the heap size reduced by one — the last element is now in its correct sorted
position and won’t be part of the heap in the next step.
3.Apply heapify to the root element to restore the Max Heap property within the reduced heap.
By continuing this process, the largest remaining element is placed in its correct position during
each iteration. Once complete, the array is sorted in ascending order.
Prepared by:- Kale J. N.