Heap Data Structure
A heap is a specialized binary tree-based data structure that satisfies the heap property. The heap data structure is widely used in various algorithms, particularly in applications such as priority queues, heapsort, and graph algorithms like Dijkstra's shortest path.
The heap can be implemented as either a max-heap or a min-heap, depending on whether the largest or smallest element is given priority. Heaps are efficient for retrieving the maximum or minimum element in constant time, making them highly suitable for certain tasks that require frequent access to the highest or lowest value.
A heap is a complete binary tree, which means:
The heap also satisfies the heap property, which differs depending on whether it is a min-heap or max-heap:
The root of the heap is always either the maximum (in a max-heap) or the minimum (in a min-heap).
Max-Heap: In a max-heap, the key of each node is greater than or equal to the keys of its children. This ensures that the largest element is always at the root of the heap.
Min-Heap: In a min-heap, the key of each node is less than or equal to the keys of its children. This ensures that the smallest element is always at the root of the heap.
There are several fundamental operations that can be performed on a heap:
Each of these operations can be performed efficiently, typically in O(log n) time.
Inserting a new element into a heap involves:
Deleting the root element (the maximum in a max-heap or the minimum in a min-heap) involves:
The heapify operation is used to rearrange an array into a valid heap. It’s a bottom-up process where we start from the last non-leaf node and move upward, applying the "bubbling down" operation to ensure the heap property is satisfied.
Heap Sort is a comparison-based sorting algorithm that works by:
Heap sort has a time complexity of O(n log n), making it efficient for large datasets.
Here’s a Python implementation of a max-heap with basic operations like insertion, deletion, and heapify:
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def heapify_up(self, i):
while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
i = self.parent(i)
def heapify_down(self, i):
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self.heapify_down(largest)
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap) - 1)
def delete_max(self):
if len(self.heap) == 0:
return None
max_value = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self.heapify_down(0)
return max_value
def peek(self):
return self.heap[0] if self.heap else None
def display(self):
print(self.heap)
# Example usage
heap = MaxHeap()
heap.insert(10)
heap.insert(20)
heap.insert(5)
heap.insert(30)
print("Heap after insertions:")
heap.display() # Output: [30, 20, 5, 10]
print("Max value:", heap.delete_max()) # Output: 30
heap.display() # Output: [20, 10, 5]