Heaps: Understanding Insertion and Deletion with Code Examples and Complexity Analysis by Mr. John Doe

Introduction to Heaps

A heap is a specialized tree-based data structure that satisfies the heap property:

• In a Max-Heap, for any given node I, the value of I is greater than or equal to the values of its children.
• In a Min-Heap, for any given node I, the value of I is less than or equal to the values of its children.

Heaps are primarily used to implement priority queues because they provide efficient access to the highest (or lowest) priority element. Two main operations performed in heaps are insertion and deletion.

Insertion in a Heap

Inserting an element into a heap involves the following steps:

1. Add the new element at the end of the heap (i.e., at the leftmost empty position in the last level).
2. Heapify Up: This step restores the heap property by comparing the added element with its parent and swapping them if the heap property is violated.

Algorithm

The process to insert a new element into the heap of size n is as follows:

1. Insert the new element at the end of the array that represents the heap.
2. Compare the new element with its parent:

• For a Max-Heap, if the new element is larger than its parent, swap them.
• For a Min-Heap, if the new element is smaller than its parent, swap them.

1. Repeat the comparison and swapping steps until the heap property is restored or the element reaches the root.

Code Implementation

Here’s a Python implementation for insertion in a Max-Heap:

def heapify_up(heap, index):
    parent_index = (index - 1) // 2
    if index > 0 and heap[index] > heap[parent_index]:
        # Swap and continue heapifying up
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_up(heap, parent_index)

def insert(heap, value):
    heap.append(value)  # Add value at the end
    heapify_up(heap, len(heap) - 1)  # Restore heap property

Example

Let's insert the element 15 into a Max-Heap represented as [20, 18, 10, 8, 7, 9, 4].

1. Insert 15 at the end: [20, 18, 10, 8, 7, 9, 4, 15].
2. Since 15 > 8, swap 15 and 8.
3. The heap after insertion is [20, 18, 10, 15, 7, 9, 4, 8].

Deletion in a Heap

Deleting an element from a heap generally refers to deleting the root node (the maximum or minimum element in the heap). The steps for deletion in a heap are:

1. Replace the root element with the last element in the heap.
2. Remove the last element from the heap.
3. Heapify Down: Restore the heap property by moving the new root element down to its correct position.

Algorithm

For deleting the root element in a heap of size n:

1. Swap the root element with the last element.
2. Remove the last element (now at the root position).
3. Apply heapify down from the root element to restore the heap property:

• For a Max-Heap, swap the element with the larger of its children if it's smaller than that child.
• For a Min-Heap, swap the element with the smaller of its children if it's larger than that child.

1. Repeat the process until the heap property is restored.

Code Implementation

Here’s a Python code to delete the root from a Max-Heap:

def heapify_down(heap, index):
    largest = index
    left_child = 2 * index + 1
    right_child = 2 * index + 2

    # Compare with left child
    if left_child < len(heap) and heap[left_child] > heap[largest]:
        largest = left_child

    # Compare with right child
    if right_child < len(heap) and heap[right_child] > heap[largest]:
        largest = right_child

    # Swap and continue heapifying down if the root is not the largest
    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        heapify_down(heap, largest)

def delete_root(heap):
    # Replace root with the last element
    heap[0] = heap[-1]
    heap.pop()  # Remove the last element
    heapify_down(heap, 0)  # Restore heap property

Example

Consider a Max-Heap represented as [20, 15, 10, 8, 7, 9, 4]. Let’s delete the root (20):

1. Replace root with last element: [4, 15, 10, 8, 7, 9].
2. Perform heapify down on the new root (4).
3. Swap 4 with 15, resulting in [15, 4, 10, 8, 7, 9].
4. Swap 4 with 8, yielding [15, 8, 10, 4, 7, 9].

Complexity Analysis

• Insertion:
• Time Complexity: O(log n), as it takes at most log n swaps to restore the heap property.
• Space Complexity: O(1) for the in-place operation.
• Deletion:
• Time Complexity: O(log n), due to the need for heapify down.
• Space Complexity: O(1) for in-place deletion.

Summary

• Insertion in Heap: Add the element to the end and heapify up.
• Deletion in Heap: Replace the root with the last element, remove it, and heapify down.
• Heaps are efficient for priority queue operations, providing O(log n) time complexity for both insertion and deletion.