We’ll look at two types of heaps: max-heap and min-heap. The root node (top-most node) of a min-heap contains the smallest value. Each child is larger than the parent. Once the heap was built in the previous example, a min-heap can be constructed from it. To build a min-heap, we’ll start from the floor(n/2) node. The reason for the floor is due to uneven number of nodes. If the number of nodes was 7, the starting position would be at floor(7/2) = floor(3.5) = 3. For our example, there are 6 nodes: floor(6/2) = floor(3) = 3 The starting position will be at the third
Tag: Min-Heap
Visually Explained Algorithms I’ll begin by stating that inserting a node into the min-heap has been outlined in my other articles: Constructing Min-Heap from a Tree and Constructing Min-Heap from an Array. As a quick recap, you add it as the last element in the tree. You compare it with its parent, and if its larger, you swap the parent and the child. You keep comparing it with each parent going up the tree until you reach a point where either the parent is smaller than the node you’re inserting, or the node has reached the root. We’ll start by deleting the root