Advanced Data Structures

In this tutorial, we'll explore Advanced Data Structures in Python. These structures help organize and manage data efficiently for complex problems. Python provides built-in and external libraries to handle these data structures.

Heaps (Priority Queues)

  • A heap is a binary tree used for managing priority queues.
  • A min-heap ensures the smallest element is always at the root, while a max-heap keeps the largest at the root.

Python uses the heapq module for heaps. By default, it provides a min-heap.

Example:

Python
Copy
import heapq

numbers = [4, 1, 7, 3, 8, 5]
heapq.heapify(numbers)  # Convert list to a heap
print(numbers)  # Output: [1, 3, 5, 4, 8, 7]

heapq.heappush(numbers, 2)  # Add element to the heap
print(numbers)  # Output: [1, 2, 5, 4, 8, 7, 3]

smallest = heapq.heappop(numbers)  # Remove the smallest element
print(smallest)  # Output: 1

Stacks and Queues

What is a Stack?

  • A stack follows the LIFO (Last In, First Out) principle.
  • Example: Undo operation in text editors.

Use a list to implement a stack.

Python
Copy
stack = []
stack.append(10)  # Push
stack.append(20)
print(stack.pop())  # Output: 20 (Last In, First Out)

What is a Queue?

  • A queue follows the FIFO (First In, First Out) principle.
  • Example: Managing tasks in a printer queue.

Use collections.deque for queues.

Python
Copy
from collections import deque

queue = deque()
queue.append(10)  # Enqueue
queue.append(20)
print(queue.popleft())  # Output: 10 (First In, First Out)

Linked Lists

  • A linked list is a sequence of nodes where each node points to the next node.
  • Unlike lists, linked lists are dynamic and don’t require contiguous memory.

    • Python
    Copy
    class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def display(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

ll = LinkedList()
ll.insert(10)
ll.insert(20)
ll.display()  # Output: 20 -> 10 -> None

    Hash Tables

    • A hash table stores key-value pairs for fast lookups.
    • In Python, the built-in dict is a hash table.

    Example:

    Python
    Copy
    # Using Python dictionary
hash_table = {}
hash_table['name'] = 'Alice'
hash_table['age'] = 25

print(hash_table['name'])  # Output: Alice

    Trees

    • A tree is a hierarchical data structure with a root node and child nodes.
    • A binary tree has at most two children per node.
    Python
    Copy
    class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Creating a binary tree
root = Node(10)
root.left = Node(5)
root.right = Node(20)

# Traversing the tree (In-order)
def in_order_traversal(node):
    if node:
        in_order_traversal(node.left)
        print(node.value, end=" ")
        in_order_traversal(node.right)

in_order_traversal(root)  # Output: 5 10 20

    Graphs

    • A graph consists of nodes (vertices) connected by edges.
    • Used for modeling networks (social networks, maps, etc.).

    Example: (Using an Adjacency List)

    Python
    Copy
    graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Traversing the graph (DFS)
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

dfs(graph, 'A')  # Output: A B D C

    Tries (Prefix Trees)

    • A trie is a tree used to store strings for efficient prefix searches.
    • Example: Autocomplete in search engines.

    Example:

    Python
    Copy
    class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # Output: True
print(trie.search("hell"))   # Output: False

    Advanced Iterators with itertools

    The itertools module provides powerful tools for advanced iteration.

    Examples:

      combinations(): Generate all combinations. permutations(): Generate all permutations. chain(): Combine multiple iterables.
    Python
    Copy
    from itertools import combinations, permutations, chain

# Combinations
print(list(combinations([1, 2, 3], 2)))  # Output: [(1, 2), (1, 3), (2, 3)]

# Permutations
print(list(permutations([1, 2, 3], 2)))  # Output: [(1, 2), (1, 3), ...]

# Chain
print(list(chain([1, 2], [3, 4])))  # Output: [1, 2, 3, 4]