Heaps Data Structure

• Heaps are tree-based data structures that follow the heap property

Heap Property

• Min-Heap: Each node's value is greater than or equal to its parent's value; the minimum element is at the root
• Max-Heap: Each node's value is less than or equal to its parent's value; the maximum element is at the root

Common Types of Heaps

• Binary Heap
• Binomial Heap
• Fibonacci Heap

Binary Heap

• A binary heap is a heap data structure shaped like a complete binary tree

Basic Heap Operations

• Insertion
• Deletion
• Find-min/max
• Increase/Decrease key
• Heapify (build heap)

Heap Implementation

• Heaps can be implemented using arrays or trees
• Array implementation is more space-efficient

Array Representation

• For a node at index i:
  • Left child: $2i + 1$
  • Right child: $2i + 2$
  • Parent: $\lfloor \frac{i-1}{2} \rfloor $

Heap Applications

• Priority Queues: Implemented using heaps, processing elements based on priority; examples include task scheduling and Dijkstra’s algorithm
• Heap Sort: Efficiently sorts an array with $O(n \log n)$ time complexity
• Graph Algorithms: Used in algorithms like Prim’s for minimum spanning tree
• Order Statistics: Finds the k-th smallest or largest element in an array

Heap Sort

• Heap sort is a comparison-based sorting algorithm using a binary heap data structure

Heap Sort Steps

• Build a max-heap from the input data
• Replace the root (largest item) with the last item in the heap, reduce the heap size by 1, and heapify the root
• Repeat while the heap size is greater than 1

Time Complexity

• Building the heap: $O(n)$
• Sorting: $O(n \log n)$
• Overall: $O(n \log n)$

Advantages of Heap Sort

• Efficiency: $O(n \log n)$ time complexity for average and worst cases
• Space Complexity: In-place sorting algorithm requiring minimal additional memory
• Guaranteed Performance: Provides guaranteed $O(n \log n)$ performance

Disadvantages of Heap Sort

• Not Stable: The relative order of equal elements may not be preserved
• Less Cache-Friendly: Tends to have more cache misses compared to algorithms like merge sort