IMG_2559.jpeg

# Lecture 25: November 19 ## Topics ### 1. Introduction to Heaps * What are heaps? * Heap operations * Heap implementation * Heap applications ### 2. Heap Sort ## What are Heaps? ### Definition: A heap is a tree-based data structure that satisfies the heap property: * **Min-Heap:**...

# Lecture 25: November 19 ## Topics ### 1. Introduction to Heaps * What are heaps? * Heap operations * Heap implementation * Heap applications ### 2. Heap Sort ## What are Heaps? ### Definition: A heap is a tree-based data structure that satisfies the heap property: * **Min-Heap:** The value of each node is greater than or equal to the value of its parent, with the minimum value element at the root. * **Max-Heap:** The value of each node is less than or equal to the value of its parent, with the maximum value element at the root. ### Common Types of Heaps: * Binary Heap * Binomial Heap * Fibonacci Heap ## Binary Heap A binary heap is a heap data structure that takes the shape of a complete binary tree. **Figure 1:** Max-Heap and Min-Heap **Figure 1**: Shows a max-heap and min-heap. The max-heap has the largest element at the root, with each parent node being larger than its children. The min-heap has the smallest element at the root, with each parent node being smaller than its children. ## Basic Heap Operations * Insertion * Deletion * Find-min/max * Increase/Decrease key * Heapify (build heap) ## Heap Implementation Heaps can be implemented using arrays or trees. The 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 $ ## Example: Consider the following array representation of a max-heap: ``` [90, 80, 70, 30, 20, 60, 50] ``` Here: * The root is 90. * The left child of 90 is 80, and the right child is 70. * The parent of 60 (index 5) is 80 (index $\lfloor \frac{5-1}{2} \rfloor = 2 $). ## Heap Applications 1. Priority Queues: * Heaps are commonly used to implement priority queues, where elements are processed based on their priority. * Examples include task scheduling and Dijkstra’s algorithm for finding the shortest path. 2. Heap Sort: * Heaps can be used to sort an array efficiently. * It has a time complexity of $O(n \log n)$. 3. Graph Algorithms: * Heaps are used in various graph algorithms, such as Prim’s algorithm for finding the minimum spanning tree. 4. Order Statistics: * Heaps can be used to find the k-th smallest or largest element in an array. ## Heap Sort Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is similar to selection sort, where we first find the maximum element and place it at the end. ### Steps: 1. Build a max-heap from the input data. 2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap, then reduce the size of the heap by 1. Finally, heapify the root of the tree. 3. Repeat the above steps while the size of the heap is greater than 1. ### Time Complexity: * Building the heap: $O(n)$ * Sorting: $O(n \log n)$ * Overall: $O(n \log n)$ ## Example: Consider the array: \[12, 11, 13, 5, 6, 7] 1. Build a max-heap: **(a) Input Array** **(b) Corresponding Heap** **(a) Input Array**: Shows the initial unsorted array \[12, 11, 13, 5, 6, 7]. **(b) Corresponding Heap**: Illustrates the max-heap built from the input array. The root is 13, and the heap property is maintained. 2. Perform Heap Sort: **(a) After First Swap** **(b) After Second Swap** **(a) After First Swap**: The largest element (13) is swapped with the last element (7), and the heap is re-heapified. **(b) After Second Swap**: The next largest element (12) is swapped with the last element (5), and the heap is re-heapified again. After several swaps and heapify operations, the array becomes sorted \[5, 6, 7, 11, 12, 13]. ## Advantages of Heap Sort: * Efficiency: * Heap sort has a time complexity of $O(n \log n)$ for both average and worst cases. * Space Complexity: * Heap sort is an in-place sorting algorithm, which means it requires minimal additional memory. * Guaranteed Performance: * Unlike quicksort, heap sort provides guaranteed $O(n \log n)$ performance. ## Disadvantages of Heap Sort: * Not Stable: * Heap sort is not a stable sorting algorithm, meaning that the relative order of equal elements may not be preserved. * Less Cache-Friendly: * Heap sort tends to have more cache misses compared to algorithms like merge sort. ## Conclusion * Heaps are a versatile data structure with various applications. * Heap sort is an efficient comparison-based sorting algorithm. * Understanding heaps and their operations is essential for algorithm design and optimization.