Heaps

Heaps

A heap is a special tree-based data structure that satisfies the heap property. Heaps are primarily used to implement priority queues, which allow for efficient retrieval and management of the largest or smallest element. Heaps are binary trees with a particular ordering between parent nodes and child nodes.

Key Characteristics of Heaps

1. Binary Tree Structure: A heap is a complete binary tree. This means that every level, except possibly the last, is fully filled, and all nodes are as far left as possible.
2. Heap Property: The heap property ensures that:
   • In a max-heap, the key of each node is greater than or equal to the keys of its children.
   • In a min-heap, the key of each node is less than or equal to the keys of its children.
3. Efficient Operations: Heaps provide efficient operations like insertion, deletion, and finding the maximum or minimum element.

Types of Heaps

1. Max-Heap:

   • In a max-heap, the value of each node is greater than or equal to the values of its children.
   • The largest element is always at the root.

   Heap Property for Max-Heap:

   • For any node $i$, the key of $i$ is greater than or equal to the keys of its children. Mathematically, for a node at index $i$, the values at the indices of the children (left and right) must satisfy:
     • $A[i] \geq A[2i+1]$ (left child)
     • $A[i] \geq A[2i+2]$ (right child)

   Use Cases: Max-heaps are used in applications like priority queues, heap sort, and finding the k-th largest element in a list.

2. Min-Heap:

   • In a min-heap, the value of each node is less than or equal to the values of its children.
   • The smallest element is always at the root.

   Heap Property for Min-Heap:

   • For any node $i$, the key of $i$ is less than or equal to the keys of its children. Mathematically, for a node at index $i$, the values at the indices of the children (left and right) must satisfy:
     • $A[i] \leq A[2i+1]$ (left child)
     • $A[i] \leq A[2i+2]$ (right child)

   Use Cases: Min-heaps are used for applications like priority queues, dijkstra’s shortest path algorithm, and finding the k-th smallest element in a list.

Heap Operations

1. Insertion:

   • Insertion in a heap starts by adding the new element at the last position of the tree (the next available position at the last level).
   • After insertion, the heap property may be violated, so the new element is bubbled up (or heapified up) to restore the heap property.

   Insertion Complexity: $O(\log n)$, where $n$ is the number of elements in the heap.

2. Extraction (Removing the Root):

   • The root (maximum for max-heap, minimum for min-heap) is removed.
   • The last element in the tree is moved to the root.
   • To restore the heap property, the element is heapified down (or bubbled down), which involves comparing it to its children and swapping it with the larger child (in a max-heap) or the smaller child (in a min-heap) until the heap property is restored.

   Extraction Complexity: $O(\log n)$, where $n$ is the number of elements in the heap.

3. Peek (Finding the Root):

   • This operation simply returns the root element without removing it. It allows us to find the maximum (in a max-heap) or the minimum (in a min-heap) element in constant time.

   Peek Complexity: $O(1)$

4. Heapify:

   • Heapify is a process that takes an unsorted array and converts it into a heap. This can be done in a bottom-up fashion by ensuring that each node follows the heap property.
   • For an array of $n$ elements, heapify can be done in $O(n)$ time, which is more efficient than repeatedly inserting elements one by one.

   Heapify Complexity: $O(n)$

5. Build Heap:

   • The Build-Heap operation takes an array of $n$ elements and arranges them into a valid heap.
   • This is typically done using a bottom-up approach where we call heapify on each subtree starting from the last non-leaf node and moving upwards to the root.

   Build Heap Complexity: $O(n)$

Properties of Heaps

1. Complete Binary Tree:

   • Heaps are complete binary trees, meaning every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

2. Efficient for Priority Queues:

   • A heap is the perfect data structure for a priority queue, which is a data structure that supports:
     • Insertions: $O(\log n)$
     • Extract-Min/Extract-Max: $O(\log n)$
     • Peek: $O(1)$

3. Heap Sort:

   • Heaps can be used to perform heap sort, a comparison-based sorting algorithm. The heap sort algorithm works by:
     1. Building a max-heap from the input data.
     2. Repeatedly extracting the maximum element from the heap (which is at the root) and placing it at the end of the array.
     3. Restoring the heap property for the remaining elements.

   Heap Sort Complexity: $O(n \log n)$, but it is not a stable sort.

4. Space Complexity:

   • Heaps use an array representation for the binary tree, so the space complexity is $O(n)$, where $n$ is the number of elements in the heap.

Example: Max-Heap Operations

Let's walk through an example of inserting elements into a max-heap and performing an extraction.

Inserting 10, 20, 5, 30, 15 into an empty Max-Heap:

1. Insert 10: The heap is now just [10].
2. Insert 20: Insert 20 at the next available position. Now, [10, 20]. Since 20 is greater than 10, we swap them. The heap becomes [20, 10].
3. Insert 5: Insert 5. The heap is [20, 10, 5]. No further changes needed as the heap property is maintained.
4. Insert 30: Insert 30. The heap is [20, 10, 5, 30]. Since 30 is greater than 20, we swap them, resulting in [30, 10, 5, 20].
5. Insert 15: Insert 15. The heap becomes [30, 10, 5, 20, 15]. No swaps are needed.

Heap after all insertions: [30, 20, 5, 10, 15]

Extracting the root (maximum element 30):

1. Remove 30 (the root), replace it with the last element (15).
2. Heap after replacement: [15, 20, 5, 10].
3. Perform heapify to restore the heap property:
   • 15 is smaller than 20, so swap them: [20, 15, 5, 10].
   • 15 is smaller than 10, so swap them again: [20, 10, 5, 15].

Heap after extraction: [20, 10, 5, 15]

Summary of Heap Operations

• Insertion: Insert an element at the last position and bubble up to maintain the heap property. Time complexity: $O(\log n)$.
• Extraction (Remove Root): Remove the root, replace it with the last element, and heapify down. Time complexity: $O(\log n)$.
• Peek: Return the root element in constant time. Time complexity: $O(1)$.
• Heapify: Convert an unsorted array into a valid heap in $O(n)$ time.
• Build Heap: Build a heap from an array of elements in $O(n)$ time.

Heaps are essential data structures used in many algorithms and applications, particularly in priority queues and sorting.