Heap Data Structure
What is Heap Data Structure?
A heap is a (Almost complete Binary Tree- ACBT) tree where each parent node is
greater than or equal to its child nodes in a max-heap or less than or equal to its
child nodes in a min-heap. This means the largest or smallest value is always at the
top (root) of the tree.
Types of Heap Data Structure
There are two main types of heaps: Max-Heap and Min-Heap in data structure.
1. Max-Heap
In a max-heap, each parent node is greater than or equal to its child nodes. This
ensures that the largest value is always at the root of the tree.
MAX-HEAP
2. Min-Heap
In a min-heap, each parent node is less than or equal to its child nodes. This ensures that
the smallest value is always at the root of the tree.
MIN-HEAP
Properties of Heap Data Structure
1. Complete Binary Tree
A heap is always a complete binary tree, meaning:
All levels are fully filled except possibly the last level.
The last level is filled from left to right.
This property ensures that the tree remains balanced, which is crucial for maintaining the
efficiency of heap operations.
. Heap Order Property
The heap must satisfy the heap order property, which differs for max-heaps and min-heaps:
Max-Heap Order Property: In a max-heap, each parent node is greater than or
equal to its child nodes. This ensures that the largest element is always at the root.
Min-Heap Order Property: In a min-heap, each parent node is less than or equal to
its child nodes. This ensures that the smallest element is always at the root.
Heap Operations
Some of the important operations performed on a heap are described below
along with their algorithms.
Heapify
Heapify is the process of creating a heap data structure from a binary tree. It
is used to create a Min-Heap or a Max-Heap.
Insert Element into Heap
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
1. Insert the new element at the end of the tree.
Insert
at the end
2. Heapify the tree.
Heapify
the array
For Min Heap, the above algorithm is modified so that parentNode is always
smaller than newNode .
Delete Element from Heap
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
1. Select the element to be deleted.
Select
the element to be deleted
2. Swap it with the last element.
Swap with the last element
3. Remove the last element.
Remove the last element
4. Heapify the tree.
Heapify the array
For Min Heap, above algorithm is modified so that both childNodes are greater
smaller than currentNode .
Peek (Find max/min)
Peek operation returns the maximum element from Max Heap or minimum
element from Min Heap without deleting the node.
For both Max heap and Min Heap return rootNode
Advantages of Heap Tree in Data Structure
Efficient priority queue operations (O(log n) for insertion and deletion)
Memory-efficient with contiguous storage
Suitable for heap sort (O(n log n) time complexity)
Effective for dynamic datasets
Supports quick access to minimum/maximum elements
