Data Structures & Algorithms · Part 1 Sep 2, 2023 4 min read

Heap Data Structures (Part 1)

Complete Binary Tree

A complete binary tree is a tree in which all levels are completely filled, except possibly the lowest one, which is filled from the left. !Complete vs Incomplete Binary Trees: a complete tree has all nodes filled left-to-right on its bottom level, unlike an incomplete tree

Heap

A heap is a special complete binary tree that is divided into two types:

Max-Heap: Every node in the tree must have a value that is greater than or equal to the values of its child nodes. This rule applies to the root node as well as every other node in the tree. Thus, the root node will always contain the greatest element.
Min-Heap: Every node in the tree must have a value that is less than or equal to the values of its child nodes. This rule applies to the root node as well as every other node in the tree. Thus, the root node will always contain the smallest element.

!Min-Heap and Max-Heap Examples: illustrating the ordering rules for min and max heaps

NOTE
The above ordering is not the only possible way to form a heap. For example, if you swap the positions of 56 and 72 in the min-heap above, it remains a valid min-heap.

How to store a heap?

Heaps can be stored dynamically using a standard pointer-based tree structure:

struct Node {
    int data;
    Node* left;
    Node* right;
};

However, because heaps are complete binary trees (and therefore have no "gaps" in their level layout), we can simplify this representation and store them sequentially in a flat array. !Heap Array Representation: mapping node levels to sequential indices in an array In this array representation:

The root node is at index 0.
For any parent node at index i, its left child is at index 2 * i + 1.
Its right child is at index 2 * i + 2.
Its parent node is located at index (i - 1) / 2.

Operations Associated with Min-Heap

For the remainder of this series, we will focus specifically on the min-heap. Max-heaps use the exact same principles, only with reversed comparison operators. The two main operations associated with a min-heap are: 1. Inserting an element 2. Removing the minimum element

1. Inserting an Element

To insert a new element, we place it at the bottom-most available position on the left of the tree (which corresponds to the last index in the array). However, this might violate the heap ordering property. To restore the heap, we bubble the element up (heapify up): we compare it with its parent, and if it is smaller, we swap them. We repeat this process until the element reaches its correct position. Let's trace inserting node 8 into a min-heap: 1. Insert node 8 at the bottom-most available position. 2. Since 8 is smaller than its parent 25, we swap them. 3. We compare 8 with its new parent 10. Since 8 < 10, we swap them again. 4. Now 8 is at the root and has no parent, so the bubbling stops. !Heap Insertion Flow: step-by-step bubble-up process swapping 8 with 25, then 10

2. Removing the Minimum Element

The minimum element is always at the root of the tree (index 0 in the array). When we remove the root, it leaves an empty spot. We fill this spot with the last element in the array (the bottom right-most node). To restore the heap property, we bubble this element down (heapify down): we compare it with its children and swap it with the smaller of the two. We repeat this process until the element is smaller than both its children. Let's trace removing the minimum element 6 from a min-heap: 1. We remove the root node 6 and swap it with the last node 72. 2. Since 72 violates the min-heap property at the root, we bubble it down. We compare 72 with its children 10 and 15, swapping it with the smaller child (10). 3. We compare 72 with its new children 22 and 25, swapping it with the smaller child (22). 4. Now 72 is smaller than its children (if any), so the bubbling stops. !Heap Removal Flow: step-by-step bubble-down process swapping 72 with 10, then 22

Complexities

Because a complete binary tree of n elements has a height of log(n), all insertions and deletions require at most O(log n) comparisons and swaps. | Operation | Time Complexity | Space Complexity |

Operation	Time Complexity	Space Complexity
Insert	`O(log n)`	`O(1)`
Remove Min	`O(log n)`	`O(1)`
Get Min	`O(1)`	`O(1)`

Conclusion

In this part, we covered the core concepts and visual operations of the heap data structure. The next part covers how to implement this dynamic structure natively in C++.

Shreyansh Jain.

404