The heap denotes an ordered binary tree. A heap can be built from a one-dimensional array. In this one-dimensional array: n represents the index of the parent node (n = 1, 2, 3, …) 2n represents the index of the left child 2n + 1 represents the index of the right child If we have the following array, we can construct a heap from it following the rules outlined above. Since there are 6 elements, the heap will have 6 nodes. Although the indices of the array start at 0, when numbering the elements in the heap, the first element starts
Articles
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
We looked at the construction of the min-heap tree from an already constructed tree. Min-heap can also be constructed directly from an array. If we look at the array that we used in the Creating a Heap from an Array article, we’ll see how easy it is to construct a min-heap from the array. We start by adding the first node, 7. Heaps are built from left to right. The next element that’s added is 2. Since we’re constructing a min-heap, all the children nodes must be smaller than the parent node. Number 2 is smaller than 7, so the two nodes are swapped. Next, element 9 is
The root node of a max-heap contains the largest value. Each child is smaller than the parent. We’ll start with the same array that we had in the previous few articles. We’ll first construct the heap. Next, we’ll start constructing the max-heap. Just like when we were constructing the min-heap, we’ll start with the 3rd node: floor(6/2) = floor(3) = 3 Since 9 has only one child node, 9 will be compared to 3. If the parent is less than the child, the nodes will be swapped. Since 9 is larger than 3, the nodes are not swapped. We move to the
Let’s use the same array that we used to construct the min-heap to create the max-heap from an array. We start by adding the first node, 7. We move top-to-bottom, left-to-right and we add the 2nd node, 2. Since 7 is larger than 2, the nodes remain in their current position. Next, 9 is added to the heap. Since 9 is larger than 7, the two nodes are swapped. Next, 4 is added as a child of 2. Since 4 is larger than 2, the two nodes are swapped. We observe that 4 moved up, so 4 is also compared to 9.
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
Visually Explained Algorithms Now that we know how to create a max-heap, we’ll move into sorting an array of values using heap sort. To sort the array using heap sort, we’ll keep creating max-heaps. Each time a max-heap is created, the root is removed and is considered sorted. Let’s start with the following example. The first step is to construct a tree from the array. We’ll follow the same procedure as outlined in my other article, Constructing Max-Heap from a Tree. To begin, 5 is swapped with 9 and then 5 is swapped with 7 to generate a max-heap. Considering that the
Visually Explained Algorithms The Selection Sort algorithm sorts an array by looking for the smallest item and moving it to the front of the list. That’s really all you have to know. Let’s jump into an example. Selection Sort starts by setting the first value as the minimum value. It then starts comparing it with each value in the array. If a lower value is found, the minimum value is updated, and the traversal continues until the end of the array is reached. During the first comparison, the value at index 1 is compared to the minimum value. Since the
Visually Explained Algorithms The adjacency matrix is a square matrix that’s used to represent a graph. The elements that are next to each other represent adjacent vertices. Why would you want to create an adjacency matrix? To save time. The adjacency matrix is much more efficient when trying to figure out the adjacent nodes in a graph. Let’s look at an example of how someone would create an adjacency matrix from a directed graph. Although the graph looks complicated, creating an adjacency matrix is a simple process. Since there are 6 vertices, the adjacency matrix will have 6 rows and
Visually Explained Algorithms The adjacency list is another way to represent adjacent vertices. Why would you want to create an adjacency list? Again, to save time. The adjacency list is much more efficient when trying to figure out the adjacent nodes in a graph. Adjacency list also takes up less space than the adjacency matrix. In the adjacency matrix, each node must contain a value, regardless of whether it contains an edge to another node or not. The adjacency list only contains nodes that are connected. Let’s look at an example of how someone would create an adjacency list from