Heap: A Detailed Overview

Heaps are a specialized tree-based data structure primarily implemented in priority queues and efficient sorting algorithms. They are binary trees that maintain a specific order between parent and child nodes, which makes them ideal for certain types of data access operations, such as quickly finding the minimum or maximum element.

What is Heap Data Structure?

A heap is a binary tree-based data structure that follows the heap property. In a heap, the value of each node is compared to the values of its children in a specific way

Heap property

1. Min Heap: The value of the parent node is smaller than or equal to its child nodes. The smallest value is found at the root of the tree.
2. Max Heap: The value of the parent node is greater than or equal to its child nodes. The largest value is at the root.

This property guarantees that the largest (in a max-heap) or smallest (in a min-heap) value is always at the root, and the tree maintains a specific order based on the heap type.

Types of Heaps

There are two main types of heaps:

• Max Heap: The root node contains the maximum value, and the values decrease as you move down the tree.
• Min Heap: The root node contains the minimum value, and the values increase as you move down the tree.

Power of heap

A sorted array and a heap can find the maximum or minimum element in O(1) time among the data structures listed. However, a heap has an O(log N) time complexity for both insertion and deletion, whereas a sorted array has an O(N) time complexity for these operations

Read About Time Complexity

Representation of Heap

Heaps are typically represented in a few different ways, depending on the context and use case. Here are the most common methods:

Array Representation

Arrays are the most commonly used representation for heaps. They are both space-efficient and simple to implement.

Array Representation Rules:

For a node at index i:

• The left child is at index 2i + 1
• The right child is at index 2i + 2

For a child at index i:

• The parent is at index (i-1) // 2
• // To take whole number only

Linked List Representation

Each node in the heap is represented using a class with a value and references to its left and right child nodes. It offers flexibility for dynamic resizing but may require more memory due to node references.

List of Lists

In some contexts, heaps are represented using a list of lists, where each sublist contains the children of the node:

[
  [10],        # Root node
  [9, 8],     # Level 1
  [5,7,6]     # Level 2
]

Array is the most commonly used representation.

Heap Operations

Common heap operations are:

• Insert: Adds a new element to the heap while maintaining the heap property. Read
• Extract(deletion) Max/Min: Removes the maximum or minimum element from the heap and returns it. Read
• Heapify: Converts an arbitrary binary tree into a heap.

# Max-Heap data structure in Python
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < n and arr[l] > arr[largest]:
        largest = l
    
    if r < n and arr[r] > arr[largest]:
        largest = r
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def deleteNode(array, num):
    size = len(array)
    i = 0
    for i in range(size):
        if array[i] == num:
            break

    # Swap with the last element
    array[i], array[-1] = array[-1], array[i]
    array.pop()  # Remove the last element which is now the number to be deleted

    # Only run heapify if the deleted node was not the last node
    if i < len(array):
        heapify(array, len(array), i)


def insert(array,newNum):
    array.append(newNum)
    current  = len(array)-1
    
    while current > 0:
        parent = (current-1) // 2

        if array[current]>array[parent]:
            array[current],array[parent] = array[parent],array[current]
            current = parent 
        else:
            break


arr = []
insert(arr,3) 
print("Inserting element:",arr)
insert(arr,2)
print("Inserting element:",arr)
insert(arr,5)
print("Inserting element:",arr)
insert(arr,6)
print("Inserting element:",arr)
insert(arr,7)
print("Inserting element:",arr)
insert(arr,15)
print("Inserting element:",arr)
insert(arr,9)
print("Inserting element:",arr)
insert(arr,1)
print("Inserting element:",arr)
insert(arr,8)
print("Inserting element:",arr)

deleteNode(arr, 6)
print("After deleting an element:", arr)
deleteNode(arr, 9)
print("After deleting an element:", arr)
deleteNode(arr, 8)
print("After deleting an element:", arr)
deleteNode(arr, 15)
print("After deleting an element:", arr)
deleteNode(arr, 2)
print("After deleting an element:", arr)
deleteNode(arr, 7)
print("After deleting an element:", arr)
deleteNode(arr, 1)
print("After deleting an element:", arr)





#Output
Inserting element: [3]
Inserting element: [3, 2]
Inserting element: [5, 2, 3]
Inserting element: [6, 5, 3, 2]
Inserting element: [7, 6, 3, 2, 5]
Inserting element: [15, 6, 7, 2, 5, 3]
Inserting element: [15, 6, 9, 2, 5, 3, 7]
Inserting element: [15, 6, 9, 2, 5, 3, 7, 1]
Inserting element: [15, 8, 9, 6, 5, 3, 7, 1, 2]
After deleting an element: [15, 8, 9, 2, 5, 3, 7, 1]
After deleting an element: [15, 8, 7, 2, 5, 3, 1]
After deleting an element: [15, 5, 7, 2, 1, 3]
After deleting an element: [7, 5, 3, 2, 1]
After deleting an element: [7, 5, 3, 1]
After deleting an element: [5, 1, 3]
After deleting an element: [5, 3]

Heap Data Structure Applications

Heaps have various applications, like:

• Heaps are commonly used to implement priority queues, where elements are retrieved based on their priority (maximum or minimum value).
• Heapsort is a sorting algorithm that uses a heap to sort an array in ascending or descending order.
• Heaps are used in graph algorithms, such as Dijkstra’s and Prim’s, to find the shortest paths and minimum spanning trees.
• Median Finding: A min heap can be used to efficiently find the median of a stream of numbers. We can use one min heap to store the larger half of the numbers and one max heap to store the smaller half. The median will be the root of the min heap. Also, see

Conclusion

Heaps are indispensable in tasks such as priority queue implementation, sorting with heapsort, and optimizing graph algorithms like Dijkstra’s and Prim’s. Their logarithmic insertion and deletion times make them ideal for dynamic datasets, maintaining order with minimal overhead. Understanding heaps equips developers with powerful tools for managing and processing data effectively.

Resources

• TechDose
• BinaryTree
• Tree
• Programiz
• Common Heap application