Heaps in Data Structure
A basic data structure that is frequently employed in computer science, heaps are especially useful for effectively implementing priority queues. A better overview of heaps is provided here, with an example of code that highlights their introduction, relationship to Priority Queues and Abstract Data Types (ADTs), and partially ordered property:
Introduction to Heaps
In addition to satisfying two primary properties a relational characteristic known as the heap-order property and a structural condition known as the tree’s shape a heap is a specific kind of binary tree that keeps a group of objects at its places. One type of basic tree data structure is heaps. Finding extreme values, insertion, and removal are among the efficient activities made possible by heaps.
Types of Heaps
Min-Heap: The key stored at p is bigger than or equal to the key stored at p’s parent for each point p in a min-heap that is not the root. By doing this, the smallest number is always found at the tree’s base. A heap is usually a min-heap unless otherwise stated.
Max-Heap: A max-heap is a binary tree data structure that stores objects at its places and meets specified characteristics. Max-Heap strategies have parent nodes with values greater than or equal to their offspring. This means that the root node always has the biggest value. This is opposite a Min-Heap technique, which places the smallest value at the root by making the parent node less than its descendants.
According to the structural property, a heap must be a full binary tree. With the possible exception of the last level, which is filled from left to right, this indicates that every level of the tree is full. This completeness property guarantees that the height of a heap with n items is O(log n).
Relationship with Priority Queues and ADTs
The most popular use for heaps is priority queue implementation. An abstract data type (ADT) called a priority queue is used to organise and manage a group of components that have been prioritised. Items in a priority queue are arranged according to their designated priority, as opposed to the First-In, First-Out (FIFO) principle used in a normal queue. A key is supplied to indicate an element’s priority when it is added to a priority queue. The next element to be eliminated in a min-oriented priority queue is the one with the smallest key.
The heap data structure enables both insertions and removals to be completed in logarithmic time (O(log n)), making it an efficient realisation for the priority queue ADT. This is a major improvement over priority queue systems that rely on lists, which may have O(n) time for insertion or removal, depending on whether the list is kept sorted or unsorted.
Being classified as an ADT, heaps are distinguished by their actions rather than by how they are implemented. Many libraries for programming languages provide them as a standard data structure, such the heapq module in Python.
Partially Ordered Property
The heap-order property refers to a heap’s relational attribute. This feature requires every node p other than the root to have a key greater than or equal to its parent’s (for a min-heap). Along any path from root to leaf, the elements are ordered non decreasingly. However, there is no set order for components at the same level or dispersed over subtrees (and not directly related via a parent-child relationship).
Nodes’ left children aren’t necessarily bigger or smaller than their right children. A heap is called “partially ordered” for this reason. Instead of maintaining order throughout the entire structure as a sorted array or a binary search tree (where sorted order is guaranteed by an in-order traversal), it only does so along direct paths from the root. Because the minimum (or maximum) element is always stored in the root, min() (or max()) operations are effective.
Example:
The basic reasoning behind adding an element to a min-oriented heap a crucial step in putting a priority queue into practice is demonstrated in the Python code sample that follows. This illustration demonstrates how the partially ordered attribute is preserved following an addition using the upheap (or “sifting up”) operation.
import heapq
# Define a list to act as the heap
heap = []
# Insert elements into the heap
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
heapq.heappush(heap, 1)
print("Heap after insertions:", heap)
# Remove elements from the heap (always the smallest)
print("Popped element:", heapq.heappop(heap))
print("Heap after popping:", heap)
# Using heapq for a priority queue
tasks = []
heapq.heappush(tasks, (2, "Write Code"))
heapq.heappush(tasks, (1, "Fix Bug"))
heapq.heappush(tasks, (3, "Write Tests"))
print("Tasks based on priority:")
while tasks:
priority, task = heapq.heappop(tasks)
print(f"Priority {priority}: {task}")Output:
Heap after insertions: [1, 5, 20, 10]
Popped element: 1
Heap after popping: [5, 10, 20]
Tasks based on priority:
Priority 1: Fix Bug
Priority 2: Write Code
Priority 3: Write Tests