Heap

Description

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its child nodes; in a min-heap, every parent node is less than or equal to its child nodes. Heaps are often implemented as binary trees, particularly binary heaps, and are commonly used in algorithms that require quick access to the largest or smallest element, such as priority queues.

Types of Heaps

1. Binary Heap

• A complete binary tree.
• Implemented efficiently using arrays.
• Two types:
  • Min-Heap: root is the minimum value.
  • Max-Heap: root is the maximum value.

2. Binomial Heap

• Collection of binomial trees.
• Supports quick merging.

3. Fibonacci Heap

• Faster amortized time for decrease-key and merge operations.
• Used in advanced algorithms like Dijkstra’s shortest path.

Array Representation of Binary Heap

Binary heaps are typically stored in arrays:

• Parent at index i
• Left child at index 2i + 1
• Right child at index 2i + 2

Example min-heap as an array:

Index:  0   1   2   3   4
Value: [1, 3, 6, 5, 9]

Heap Operations

1. Insert

• Add element to end of array.
• “Bubble up” to maintain heap property.
• Time Complexity: O(log n)

2. Extract-Min / Extract-Max

• Remove root node.
• Move last node to root and “bubble down.”
• Time Complexity: O(log n)

3. Peek

• Return root without removing.
• Time Complexity: O(1)

4. Heapify

• Convert unordered array to a heap.
• Time Complexity: O(n)

5. Replace

• Replace root with a new value and reheapify.
• Time Complexity: O(log n)

Priority Queues with Heaps

Heaps are often used to implement priority queues, where the highest (or lowest) priority element is served before others.

Python example:

import heapq
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
print(heapq.heappop(pq))  # Output: 1

For max-heaps, negative values or custom wrappers can be used:

heapq.heappush(pq, -10)  # simulate max-heap

Heap Sort Algorithm

Heap sort is a comparison-based sorting technique based on binary heap structure.

Steps:

1. Build a max-heap from input.
2. Swap root with last node.
3. Reduce heap size and reheapify.

Time Complexity:

• Best, Average, Worst: O(n log n)
• In-place sort

Applications

• Priority Queues
• Dijkstra’s and Prim’s Algorithms
• Heap Sort
• Event Simulation Systems
• Median Maintenance

Comparison: Heap vs Other Structures

Memory and Storage

• A binary heap of n elements needs O(n) space.
• Implemented as arrays for cache efficiency.
• In languages like C++, Java, or Python, heaps use dynamic arrays.

Visualization Example

Min-Heap Tree:

      1
     / \
    3   6
   / \
  5   9

Array: [1, 3, 6, 5, 9]

Summary

A heap is a powerful data structure optimized for fast access to the minimum or maximum element. Its efficient time complexities for insertion and deletion make it ideal for scenarios where priority matters. Whether implementing scheduling systems, sorting algorithms, or pathfinding algorithms, heaps play a vital role in the performance and design of modern computing systems.