Overview

  • A heap is a specialized tree-based data structure satisfying the heap property:
    • Max-Heap: Parent nodes are greater than or equal to their children.
    • Min-Heap: Parent nodes are less than or equal to their children.
  • Heaps are commonly implemented as binary heaps using arrays.

Key Operations

  1. Insert: Add an element to the heap and maintain the heap property.
  2. Delete/Extract: Remove the root element and maintain the heap property.
  3. Heapify: Reorganize elements to maintain the heap property.

Python Implementation

Python provides a built-in heapq module for min-heaps.

Min-Heap Implementation

import heapq

# Create a Min-Heap
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)

print(heapq.heappop(min_heap))  # Output: 1

Max-Heap Implementation

Python’s heapq module doesn’t directly support max-heaps, but you can simulate one by storing negative values.

import heapq

# Create a Max-Heap
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)

print(-heapq.heappop(max_heap))  # Output: 3

Applications of Heaps

  1. Priority Queue

    • Manage elements with priorities efficiently.
    • Example: Dijkstra’s algorithm for shortest paths.

  2. Heap Sort

    • Sorting algorithm using heap operations.
    • Time Complexity: O(n log n).

  3. Kth Largest/Smallest Element

    • Use a heap to efficiently find the kth largest or smallest element in a list.

  4. Merge K Sorted Lists

    • Use a min-heap to merge multiple sorted lists efficiently.

  5. Median Finder

    • Maintain two heaps (a max-heap and a min-heap) to keep track of the median.

  6. Top K Elements

    • Use a min-heap to track the top K elements in a stream.

Common Heap Problems

1. Kth Largest Element

Find the Kth largest element in an array.

import heapq

def find_kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

# Example Usage
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k))  # Output: 5

2. Merge K Sorted Lists

Merge multiple sorted lists into one sorted list.

import heapq

def merge_k_sorted_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, element_idx = heapq.heappop(heap)
        result.append(val)
        if element_idx + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][element_idx + 1], list_idx, element_idx + 1))

    return result

# Example Usage
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
print(merge_k_sorted_lists(lists))  # Output: [1, 1, 2, 3, 4, 4, 5, 6]

3. Top K Frequent Elements

Find the K most frequent elements in an array.

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

# Example Usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent(nums, k))  # Output: [1, 2]

4. Median Finder

Maintain a running median in a data stream.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # Max-Heap for the smaller half
        self.large = []  # Min-Heap for the larger half

    def add_num(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))

        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

# Example Usage
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median())  # Output: 1.5
mf.add_num(3)
print(mf.find_median())  # Output: 2

Summary

Heaps are an efficient data structure for solving problems involving priority and ordering. With their logarithmic time complexity for insertions and deletions, they form the backbone of algorithms like Dijkstra’s and are widely used in solving real-world problems.