Mastering Data Structures and Algorithms in Python: A Complete Guide (Part 4)

 

Part 4: Advanced Data Structures - Heaps and Graphs

Heaps

Heaps are specialized tree-based data structures that satisfy the heap property. They are commonly used to implement priority queues and heap sort algorithms.

Introduction to Heaps

Heaps can be of two types:

• Min Heap: Every parent node has a value less than or equal to its child nodes.
• Max Heap: Every parent node has a value greater than or equal to its child nodes.

Heap Operations

Common operations on heaps include insertion, deletion (extract-min or extract-max), and heapify (maintaining the heap property).

Applications of Heaps

Heaps are used in various applications such as priority queues, heap sort algorithm, and scheduling algorithms due to their efficient operations.

Example of Min Heap Implementation in Python

<!-- Example: Min Heap Implementation in Python -->
<h3>Example: Min Heap Implementation in Python</h3>

<p>Python implementation of a min heap using heapq module:</p>

<pre><code>import heapq

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        heapq.heappush(self.heap, item)

    def delete_min(self):
        return heapq.heappop(self.heap)

    def peek_min(self):
        return self.heap[0]

# Example usage
min_heap = MinHeap()
min_heap.insert(3)
min_heap.insert(2)
min_heap.insert(1)

print("Min heap after insertions:", min_heap.heap)  # Output: [1, 3, 2]

print("Min element:", min_heap.delete_min())  # Output: 1
print("Heap after deletion:", min_heap.heap)  # Output: [2, 3]
</code></pre>
    

Graphs

Graphs are non-linear data structures consisting of nodes (vertices) and edges that connect these nodes. They are widely used to represent networks and relationships.

Introduction to Graphs

Graphs can be categorized into:

• Directed Graphs (Digraphs): Edges have a direction.
• Undirected Graphs: Edges do not have a direction.

Graph Representations

Graphs can be represented using:

• Adjacency Matrix: A 2D array where each cell represents if there is an edge between two nodes.
• Adjacency List: A collection of lists or dictionaries to represent edges.

Graph Traversal Algorithms

Traversal algorithms enable visiting each node in a graph. Common algorithms include:

• Breadth-First Search (BFS): Visit nodes level by level.
• Depth-First Search (DFS): Explore as far as possible before backtracking.

Example of BFS and DFS in Python

<!-- Example: BFS and DFS Implementation in Python -->
<h3>Example: BFS and DFS Implementation in Python</h3>

<p>Python implementations of BFS and DFS for an undirected graph using adjacency list:</p>

<pre><code>from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        while queue:
            node = queue.popleft()
            print(node, end=' ')
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=' ')
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

# Example usage
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

print("BFS traversal starting from node 0:")
graph.bfs(0)  # Output: 0 1 2 3

print("\nDFS traversal starting from node 0:")
graph.dfs(0)  # Output: 0 1 2 3
</code></pre>
    

Conclusion

Advanced data structures like heaps and graphs play a crucial role in solving complex algorithmic problems efficiently. Understanding their properties, operations, and practical applications is essential for any aspiring programmer or computer scientist.