Python Heap - Complete Guide to Heap Data Structures in Python

Heaps are an essential data structure in computer science, widely used for priority queues, scheduling algorithms, and more. In Python, heaps are efficiently handled using the heapq module.

What is a Heap?

A heap is a special tree-based data structure that satisfies the heap property:

• In a min-heap, the parent node is always smaller than or equal to its children.
• In a max-heap, the parent node is always greater than or equal to its children.

Heaps are often implemented using arrays, and they are commonly used in priority queues, sorting, and graph algorithms.

Python heapq Module

Python provides the heapq module, which allows efficient heap operations. This module implements a min-heap by default.

Basic Heap Operations

import heapq

# Create an empty heap
heap = []

# Push elements into the heap
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)

# Pop the smallest element
print(heapq.heappop(heap))  # Output: 5

Converting a List into a Heap

numbers = [10, 30, 20, 5, 8]
heapq.heapify(numbers)
print(numbers)  # Output: [5, 8, 20, 30, 10] (Min-Heap Order)

Implementing a Max Heap

Since heapq only provides a min-heap, we can simulate a max-heap by negating the values.

import heapq

heap = []
heapq.heappush(heap, -10)
heapq.heappush(heap, -5)
heapq.heappush(heap, -15)

print(-heapq.heappop(heap))  # Output: 15

Use Cases of Heaps in Python

• Priority Queues: Used in scheduling algorithms and Dijkstra's shortest path algorithm.
• Heap Sort: Sorting algorithm with O(n log n) complexity.
• Top K Elements: Efficiently find the k smallest or largest elements in a dataset.

Heap vs Other Data Structures

FAQs About Python Heap

1. What is the time complexity of heap operations?

Insertion and deletion in a binary heap take O(log n) time, while retrieving the smallest (or largest) element takes O(1) time.

2. Can I use a heap for sorting?

Yes! Heap sort is an efficient sorting algorithm that uses a heap to sort elements in O(n log n) time.

3. How do I implement a priority queue in Python?

The heapq module can be used to implement a priority queue where the lowest priority value is always at the top.

4. Does Python have a built-in max-heap?

No, but you can simulate a max-heap by pushing the negated values into a min-heap.