Data Structures Explained with Python

Heaps

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Heaps are of two types:

• Max-Heap: In a Max-Heap, for any given node C, if P is a parent node of C, then the value of P is greater than or equal to the value of C. As a result, the largest key is stored at the root of the tree.
• Min-Heap: In a Min-Heap, for any given node C, if P is a parent node of C, then the value of P is less than or equal to the value of C. As a result, the smallest key is stored at the root of the tree.

Applications of Heaps:

• Priority Queues: Heaps are commonly used to implement priority queues where the element with the highest (or lowest) priority is quickly accessible. Python'''s heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.
• Heap Sort: This is one of the most efficient comparison-based sorting algorithms.
• Graph Algorithms: Algorithms like Dijkstra'''s shortest path and Prim'''s minimum spanning tree algorithm use heaps to optimize their performance.

Implementation in Python:

Python'''s heapq module provides functions for working with heaps. This module implements a min-heap. To implement a max-heap, you can store negated values.

import heapq

# Min-Heap example
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 9)
print("Min-Heap:", min_heap) # Note: heapq stores it as a list, but it maintains heap property

smallest = heapq.heappop(min_heap)
print("Smallest element popped:", smallest)
print("Min-Heap after pop:", min_heap)

# To build a heap from a list in O(n) time
list_data = [5, 2, 8, 1, 9, 3]
heapq.heapify(list_data)
print("Heapified list (Min-Heap):", list_data)

# Max-Heap example (using negated values)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
print("Max-Heap (stored as negated values):", max_heap)
largest_negated = heapq.heappop(max_heap)
print("Largest element (actual value):", -largest_negated)
        

Complexity:

• Insertion (Push): O(log n)
• Deletion (Pop - root): O(log n)
• Peek (Get Min/Max): O(1)
• Heapify (Build heap from list): O(n)

Heaps offer an efficient way to manage prioritized data and are fundamental in various algorithms and systems.