Heap operations in DSA
Mainly used to create priority queues and make sorting algorithms like heapsort easier, heaps are essential data structures in computer science. A partially ordered structure that may be represented and used as a binary tree is called a heap. A heap allows for efficient insertions and removals in logarithmic time by maintaining a compromise between elements being completely unsorted and properly sorted, in contrast to a strictly sorted list.
Heaps, which are array-based, operate well with complete binary trees.Parents are (index – 1) // 2 and left and right children are 2 * index + 1 and 2. Insertion, deletion, plus peeking and traversal are heap operations.
A particular ordering property is maintained by heaps:
Min-heap: A min-heap is a binary tree data structure with parent nodes with values less than or equal to their children. The heap-order property ensures that the heap’s smallest key is always at its root. In contrast, a max-heap has the largest key at the root because the parent’s value is bigger than or equal to its children. Unspecified heaps are considered to be min-heaps.
Max-heap: A Max-heap is a tree-based data structure that orders by value, with each parent node greater than or equal to its offspring. The root of the tree always has the largest key. In contrast, a Min-heap has the lowest key at the root because the parent’s value is smaller than or equal to its children.
After any changes are made, this arrangement must be maintained.
Insertion
The entire binary tree property is maintained by first placing a new element (key-value pair) at the next accessible location when it is added to a heap. At the deepest level, this is usually the leftmost open slot; if the bottom level is already full, it is the first position of a new level.
Once the new element has been inserted, the heap-order attribute may be broken. A procedure called “up-heap bubbling” also referred to as “sifting up” or upheap is used to restore this feature.This is done by comparing the keys of the newly added element and its parent. Items are exchanged in a min-heap if the child’s key is smaller than the parent’s. Upward in the tree, this swapping continues until the element reaches the root or meets heap-order.
The heap insertion run-time efficiency is O(log n) for ‘n’ heap elements. As the element travels at most the tree’s height, which is O(log n) for a complete binary tree, the up-heap bubbling operation causes this logarithmic duration. Inserting the first array value takes O(1) time.
Python Heap Priority Queue class’s add(key, value) method creates a min-oriented priority queue from a binary heap. After adding the new item to self.data, this function calls self to bubble it up the heap.Len(self.data) – 1
Example:
class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, value):
# Add value to the end of the heap
self.heap.append(value)
self.heapify_up(len(self.heap) - 1)
def heapify_up(self, index):
parent = (index - 1) // 2
if index > 0 and self.heap[index] > self.heap[parent]:
# Swap if child is greater than parent
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self.heapify_up(parent)
def display(self):
return self.heap
# Example usage
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(20)
max_heap.insert(5)
max_heap.insert(30)
print("Heap after insertions:", max_heap.display())Output:
Heap after insertions: [30, 20, 5, 10]Deletion
You normally delete the heap’s highest or lowest priority element (like the min-heap’s minimal element), which is always at the tree’s root.
Three steps make up the deletion algorithm:
Find the index of the value to delete: For many data structures, determining the index or location of an item to remove is an essential first step in the deletion process. Depending on the structure and its underlying organisation, different methods are used to find the value.
Replace the deleted element: Replacing the deleted element involves moving the root, the final element in the heap, to the rightmost node at the deepest level. Next, we decrement the total number of elements in the heap.
Verify heap ordering: Use a “down-heap bubbling” technique (sometimes called “sifting down” or “downheap”) to confirm heap ordering. The children of the new element at the root are compared. In a min-heap, it is switched with the lesser of its offspring if it is larger than either. Until the element turns into a leaf or the heap-order property is restored, this process keeps going down.
Removal from a heap is thus O(log n) efficient. During the down-heap bubbling procedure, the element that was relocated to the root position will only travel as high as the tree.
The remove min() method in the Heap Priority Queue class illustrates this. It calls self.downheap(0) to fix the position of the new root after swapping the minimum item (at index 0) with the last item and removing the final item using pop().
Other Heap Operations
Peeking: Peeking retrieves the minimal (or maximum) key element from the heap without removing it. A min-heap’s root element (index 0). O(1) is its efficiency.
Changing Priority / Updating: Heaps can assist with operations that modify an existing element’s priority. Typically, this entails finding the element, changing its key, and then restoring the heap-order property via either an up-heap or down-heap bubbling operation. O(log n) performance is likewise attained via update(loc, k, v) and remove(loc) procedures for heap-based adjustable priority queues.
Heap Traversal
Iterating sequentially through the underlying array is the standard method for traversal in a heap when it is based on an array implementation. This method results in a run-time complexity of O(n) for looking for a specific item in a heap because, in contrast to a binary search tree, the partial ordering of a heap prevents effective direct searching of arbitrary values. The search can be viewed as a traverse that visits nodes in the array sequence in a breadth-first fashion.
Any “garbage values” that may still be present from earlier deletions in the underlying array are ignored when traversing the array; only the elements that are currently regarded as belonging to the conceptual heap are significant. Although a heap’s binary tree structure can be traversed using typical tree traversals (preorder, inorder, and postorder), the heap property is weaker than the binary search tree property, hence it is not always the case that the components are returned in sorted order. For instance, it is uncommon for a preorder traversal of a heap to list its keys in a non-decreasing sequence.
Heaps are appropriate for priority queue solutions because they provide effective O(log n) time complexity for their fundamental insertion and deletion operations. Other operations are O(1), such as determining the minimal element (min()). However, the sequential structure of array traversal needed for non-priority-based lookups means that looking for an arbitrary element that is not at the root requires O(n) time.