In data structure, a heap is a complete binary tree that satisfies the heap property. The heap property defines the ordering of elements in the tree. Depending on whether the heap is a max heap or a min heap, the ordering can be either in descending or ascending order.
Properties of Heap
1. Complete Binary Tree
A heap is a complete binary tree, which means all levels of the tree are completely filled except possibly the last level, which is filled from left to right. This property allows us to represent the heap efficiently using an array.
2. Heap Property
A max heap satisfies the following property: for any node i, the value of i should be greater than or equal to its children’s values.
In other words, the parent nodes have greater values than their children. Conversely, a min heap satisfies the opposite property: for any node i, the value of i should be less than or equal to its children’s values.
3. Parent-Child Relationship
In a binary heap, each node has at most two children.
For any node i, its left child can be found at index 2i + 1, and its right child can be found at index 2i + 2. Similarly, for any node i, its parent can be found at index (i – 1) / 2.
4. Efficient Operations
The properties of a heap make it efficient for certain operations:
- Insertion: When inserting an element into a heap, we can easily maintain the heap property by comparing the new element with its parent and swapping them if necessary. This process is known as heapify.
- Deletion: When deleting an element from a heap, we typically remove the root node.
After removing the root, we replace it with the last element in the array and perform heapify to restore the heap property.
- Heap Sort: Heap sort is an efficient sorting algorithm that utilizes the properties of a heap. It first builds a max or min heap from the input elements, then repeatedly extracts the maximum or minimum element from the heap until it is empty.
5. Priority Queue
A common application of a heap is implementing a priority queue.
In a priority queue, elements are assigned priorities, and operations such as insertion and deletion are performed based on these priorities. The heap’s ability to efficiently maintain its properties allows for efficient priority queue operations.
In conclusion, heaps are fundamental data structures that provide efficient operations for maintaining ordered collections of elements. By satisfying properties such as being a complete binary tree and maintaining either max or min heap property, heaps enable efficient insertion, deletion, sorting, and priority queue operations.