Category: Data Structure

Union Find

Posted on by NY Comdori

There are two methods in order to traverse a graph – BFS, DFS. Let’s say there is a graph problem to count the number of connected components. Here are the steps you can take.
1. Build the graph
2. Perform BFS or DFS
3. Outer loop to check each unvisited node
4. Number of calls to BFS or DFS is equivalent to the number of connected components because BFS or DFS will mark the connected component as visited

Time complexity would be O(V+E) where V is the node and E is the edge. It is linear complexity.

This is a simple problem with a simple solution: BFS or DFS works perfectly.

Now, let’s tweak the problem a little bit. Let’s say there is a stream of edges instead of the entire graph from the beginning. And you are asked to provide the number of connected components as the new edges are coming in. You have to perform BFS or DFS every time new edges come in because the new edge may or may not decrease the number of connected components. Let’s say there is an edge connecting node between u and v. Two possibilities of this edge is
1. if u, v belong to the same connected component, the number of connected components is unchanged
2. if u, v belong to the different connected components, the number of connected components will decrease by one because the component which u belongs will be connected to component which v belongs (or vice versa)

Time complexity of naive approach would be O(V+E) * O(E) = O(VE + E^2). It would be quadratic regardless this is dense or sparse graph.

The question we ask is can there be a better way to solve the problem?

Naive approach of union find

Let’s have an array to keep track of its component ids. The size of the array will be the size of the nodes each node will be assigned a component id it belongs. With the setting, when new edges come in, we look up the table and perform the following actions.
1. if they (two nodes in the edge) belong to the same component (have the same component id), then skip.
2. if they belong to different component, then update the component id.

Here is the psuedo code for the updating component id

componentid = array(size V), initialized to node id (node id will be component id)

for each edge(u,v):
    if componentid[u] != componentid[v]: // find operation
      cid = componentid[u]
      for each i in 0 to n-1: // n is number of nodes. line 6-8 is merge (or union) operation
          if componentid[i] == cid:
              componentid[i] = componentid[v]

For each edge, number of union operation is n-1. The total cost of union operation would be O(VE) which is O(V^2) assuming this is sparse graph. For each edge, number of find operation is E and the total cost of find operation would be O(E) since find operation itself is O(1). All together, the total cost would be O(V^2) + O(E) = O(V^2). The code is simpler yet the complexity is still the same because union operation is expensive. Is there any way to improve union operation?

Optimized union operation

If you think about it, we actually don’t need to iterate every single node in a component and update the id. Let’s say there is a root node in a component, then we only need to update the root node component id. Let’s take a look at the example below.

In the above graph, there will be an edge between u and v nodes. Now, when updating connected component, you only need to update component id of root node of u. Each find operation will look up the component id of root node then update. How do you find the root node of component? Just keep looking at parents where node id == parent[node id]. Find operation will not be O(1) but union operation will be O(1) now because you always update 1 node for the operation. Here is the optimized version of pseudo code.

for each edge(u,v) in edges:
    rootU = find(u)
    rootV = find(v)
    if rootU != rootV:
        componentid[rootV] = componentid[rootU]
        
function find(x):
    while componentid[x] != x:
        x = componentid[x]
    return x

Let’s look at the complexity of the operation.
The cost of each union operation is O(1) and there are O(E) edges. Total cost of union operation is O(E).
The cost of find operation is O(V) in worst case (where the tree is like a linked list, single chain) and there are O(E) edges. The total cost of find operation in worst case would be O(VE) which is O(V^2) assuming sparse graph.

We are heading to the correct direction but the time complexity didn’t improve which means there needs further optimization.

Union find with merging rules

If you blindly merge one tree to another, you might end up a single chain, linked list. The best case of tree structure would be a balanced tree where the height is O(log n). How can we achieve almost balanced tree to make find operation O(log n)?

Here is the claim of the rule:
When merging together two components, you will achieve O(log n) if you make the root of the smaller component point to the root of the larger component.

Let’s prove if the claim is correct. Let’s say there are two connected components (trees) – u and v

With the above setting, we need to prove: h <= log(N(u) + N(v)) where h is height of the new component (tree)
This will be a proof by induction.

Base case:
1. All nodes are disconnected: since all nodes are disconnected there is only one node per component. height of the component is 0 and it is true that 0 <= log 1 (only 1 node in the tree)
2. There is an edge between two nodes from step 1. In this case, h=1 and n=2. Claim is still true after first union operation.

After the above steps, there are two possible cases
1. two disconnected nodes are joined. Same as 1st step above
2. 2 nodes and 1 node join which becomes n=3, h=1 and 1 <= log3 according to the rule.

Assuming the claim is true after i union operations, we need to prove: h <= log n after i+1 union operation. Let’s note height of V tree as H(v) and height of U tree as H(u). There are two possible cases of the trees (u and v) where H(v) > H(u) or H(v) < H(u). With that said, the height of newly joined tree will be like this: h = max(H(v), H(u)+1). Note that number of nodes in V are greater than u here.

Case 1. H(v) > H(u). In this case, joining u tree to v doesn’t change the height and new height of the result tree is still H(v). We know that H(v) <= log N(v) (induction hypothesis) which also makes the following statement true H(v) <= log (N(v) + N(u)). New height h is H(v) so finally this guarantees h <= log(N(v) + N(u)).

Case 2. H(v) < H(u). h (new height) = H(u) + 1. based on induction hypothesis, we know H(u) <= log N(u) is true. Let’s add some tweak to the hypothesis: H(u) + 1 <= log N(u) + 1. H(u) + 1 is new height h. log N(u) + 1 would be log 2N(u). Then, it leads to this equality:
h <= log 2N(u). Given N(u) < N(v), this is also true: h <= log (N(u) + N(v)), which guarantees new height will be lower than log (N(u) + N(v)).

Based on the above proof, we know that the height will be always balanced if two trees are merged according to the rule.

With that said, the total complexity will be
(n-1) * cost of union op + E * cost of find op = (n-1) * O(1) + E * O(log n) = O (n log n)

Here is the pseudo code based on all the optimization

parents = a 1D array of size n
sizes = a 1D array of size n

for i in 0 to n-1:
    parents[i] = i
    sizes[i] = 1

for (u, v) in edges:
    rootU = find(u)
    rootV = find(v)
    if rootU != rootV:
        if sizes[rootU] < sizes[rootV]:
            parents[rootU] = rootV
            sizes[rootV] += sizes[rootU]
        else:
            parents[rootV] = rootU
            sizes[rootU] += sizes[rootV]
            
function find(x):
    while parents[x] != x:
        x = parents[x]
    return x

Time complexity is O(n log n), slightly slower than DFS or BFS but you don’t need to build graph for traversal. In addition to that, when graph changes dynamically, union find is better than DFS or BFS

Final optimization – Path Compression

There is one final optimization. You might have noticed that we are traversing to find the parent node every time we merge. However, what if we update the parent node id to the root node after traversing? It is slightly more work in the beginning but will save time for next root node search. In other words, we can compress the path (flattening the tree). The updated code will use recursion for simplicity.

function find(x):
    // base case
    if x == parents[x]:
        return x
        
    // recursive case
    rootX = find(parent[x])
    parent[x] = rootX
    return rootX

Time complexity of the find is still O(log n). However, with many traversals, this practically makes it O(1)

Conclusion

This is it for the union find. DFS or BFS is typically used for many graph problems. However, there are cases when DFS or BFS doesn’t work perfectly and Union Find can actually improve for the better performance with simple code. I hope this helped you understand union find better. Thank you for reading.

Leetcode 377. Combination Sum IV

Posted on by NY Comdori

This post explains how to solve leetcode 377. combination sum IV problem. It starts with brute force idea and optimize to efficiently solve the problem. Please refer to this link for problem detail.

In this problem, you have two arguments – target and nums array. You are supposed to find the number of combinations to make the target amount only using numbers in nums array. In this problem, the order matters as you see in the example.

Let’s think about brute force idea – enumerate all the possible subsets of nums array. For each subset, you also need to check how many of each number can make the target. This is very expensive with exponential time complexity.

Can we do better? Let’s suppose nums = [1,2,3] and target is 10. Now, let’s also suppose that we have collected a number of combinations right before 10. In other words, we have the result at 9, 8, 7 which are (10 – 1), (10 – 2), (10 – 3). Since the order matters, we need to count all three cases. Then, the answer would be result(10 – 1) + result(10 – 2) + result(10 – 3). We can recursively derive the same relationship for 9, 8, 7 values. Let’s take a look at the below diagram.

We just need to recursively look for children until the base case is reached, which is 0. This is better than enumerating all the subsets and finding combinations. However, there is still room to improve because there are overlapping subproblems. This overlapping subproblem is like calculating fibonacci number recursively. We prevent calculating the same subproblem by storing the result. If subproblem is found, then we just need to reuse that one. Ultimately this becomes dynamic programming.

There are two ways – bottom up, top down – to solve the problem. In this post, I will just explain bottom up approach.

Let’s define f(t) as “number of combinations based on number in nums at target amount t”

Subsequently, the recurrence relation would be f(t) = sum(f(t – nums[i])), where i is 0..nums.length() (index). If t – nums[i] < 0, then it would be 0 as you can’t have negative value.

With the recurrence relation clearly defined, the code becomes very simple. The solution is based on C++.

Base case is t=0. There is only 1 way to make amount 0 which is empty subset. Based on the base case, we need to build up from the bottom until reach the target amount.

int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned int> table(target+1);
    table[0] = 1;
    for (int i = 0; i <= target; ++i)
    {
        for (int num : nums)
        {
            if (i >= num)
            {
                table[i] += table[i-num];
            }
        }
    }

    return table[target];
}

The time complexity is O(nt) where n is length of nums and t is target amount. One gotcha is that if t is really large (ex. > 2^n) this essentially becomes same as brute force solution.

Intro to Union-Find Data Structure

Posted on by NY Comdori

Union-Find is a data structure that mimics tree data structure except that nodes point to their parent instead of children.

The union-find is very useful for set operations such as the following.
1. find – find the root of the current node
2. same component – check if two trees have the same root node. (belongs to the same set)
3. union (merge) – merge two trees (sets) into one

Such operations are very useful for problems like connected components – each node belongs to only one connected component – and vertex coloring.

The union-find is useful for algorithms such as minimum-spanning tree (Kruskal’s algorithm) – a minimum subset of edges forming a tree connecting all vertices.

How is the union-find structured?

The union-find data structure represents each subset as a reverse or backward tree that a node points to the parent instead of children.
In this example, I used an array to keep track of parent nodes efficiently and for simplicity.
But you could use hashmap to deal with a more complicated node structure.

Let’s take a look at the example below.

union find data structure example

There are two sets. (Two trees with two nodes)
The first set has 4 nodes – 2, 1, 0, 3 – where node 2 is the root node.
The other set has 1 node – 4.

As you can see from the above I have an array to keep track of the parent of each node.
For example, the parent node of node 0 is 1 and the parent node of node 1 is 2.
You can see that the value of indices 0 and 1 is the value of their parent nodes.

Algorithm

Let’s take a look at the algorithms for each union-find operation.

Find

Again, this operation checks the root node of the provided node.
For the find operation, you just need to recursively check the parent node until it reaches the root.
How do you know when it reaches the root?
In the above structure, you will see the index and the value are equal.
If you are using another data structure, which will likely be the one using a key and value, you just need to check if a key and value are the same.

Same Component

This operation checks if two nodes belong to the same tree, have the same root node.
This one is very easy once ‘Find’ operation is implemented as you just need to find the root node of both nodes and check if they are the same.

Merge

The operation merges two trees into one.
However, merging without much thought may cause an unbalanced tree and hurt overall performance.
How should we merge the tree?
You can always link the tree that has a lower height to the higher one.
For example, if you are to merge two trees in the above picture, there are only two cases.
You can merge root node 2 to 4 which will increase the height by 1.
Or you can merge root node 4 to 2 of which the height will remain the same.
Therefore you should always merge the lower tree to the higher one.

Code Example

#include <vector>

using namespace std;

class UnionFind
{
    int totalNodes;
    
    // indicates parent nodes
    vector<int> parents;
    
    // indicates number of elements in a subtree
    vector<int> numElts;
    
public:
    UnionFind(int _totalNodes) : totalNodes(_totalNodes), parents(totalNodes), numElts(totalNodes)
    {
        for (int i = 0; i < totalNodes; ++i)
        {
            parents[i] = i;
            numElts[i] = 1;
        }
    }
    
    int find(int nodeId)
    {
        if (parents[nodeId] == nodeId)
        {
            return nodeId;
        }
        else
        {
            return find(parents[nodeId]);
        }
    }
    
    bool sameComponent(int node1, int node2)
    {
        return find(node1) == find(node2);
    }
    
    void merge(int node1, int node2)
    {
        int root1 = find(node1);
        int root2 = find(node2);
        
        // already in the same component. noop
        if (root1 == root2)
        {
            return;
        }
        
        
        if (numElts[root1] >= numElts[root2])
        {
            parent[root2] = root1;
            numElts[root1] += numElts[root2];
        }
        else
        {
            parent[root1] = root2;
            numElts[root2] += numElts[root1];
        }
    }
};

Performance

Find – O(log n)
It just needs to climb the tree until it reaches the root

Same Component – O(log n)
It only needs to complete two find operations.

Merge – O(log n)
It only needs to complete two find operations.

Conclusion

The union-find is a very powerful data structure that handles set operations in a really fast time.
And the data structure itself is very simple too!
The data structure is used for many algorithms such as minimum spanning tree, Kruskal’s algorithm.

Intro to Binary Search Tree

Posted on by NY Comdori

Binary search tree is very efficient and has strengths of array and linked list.
Array and Linked List are great data structure but they have some weaknesses.
It’s fast to access array but slow to adjust the size.
It’s slow to access linked list but fast to adjust the size.
However, it’s fast to access binary search tree and it’s still very flexible to adjust the size.

What is Binary Tree?

Before diving into binary search tree we need to understand binary tree first.
Binary tree is an extended form of singly linked list but has two pointers to other nodes (children) instead.
Pointers are not to the previous and next but to left and right children.
Let’s first take a look at the picture of an example binary tree.

binary search tree

As you see the above, the topmost node is the root of the tree.
The root has two children node, left and right. (please note that you don’t have to call it left & right)
The right child node doesn’t have any child and thus it is called leaf node of the tree.

How is binary search tree different from binary tree?

The only difference between binary search tree and binary tree is the order of nodes when a node is inserted.
Binary search tree always forces the rule below.

  • Any value less than the value of the current node is always placed on the left child leaf node.
  • Any value greater than the value of the current node is always placed on the right child leaf node.
  • Move to proper child node if either child node is already created (non-leaf).

Let’s take a look at the example below for insertion.
I am going to insert 5 nodes and let’s see how the insertion is done.

I first inserted a node with value 20 which became the root of the tree since the tree was empty.
Then I inserted another node with value 10 which is the left child of the root node because 10 is less than 20.

binary search tree example

If I have another node with value 15 where will it be placed?
15 is less than 20 so it goes to the left child of the root node.
But the left child is already there so we compare 10 and 15.
15 is greater than 10 and the node with value 10 doesn’t have any right child.
Therefore, a node with value 15 will be the right child of the node with value 10. And it is a leaf node.
Please note that the node is always inserted as the leaf node of the tree.

binary search tree example

I have two more nodes with values 8 and 21 respectively.
The node with value 8 will be the left child of the node with value 10.
The node with value 21 will be the right child of the node with value 20.

Performance of Binary Search Tree

As you see the above example binary search tree always maintains the order of nodes after the insertion.
This is great since it will be very fast to find and access a certain node thanks to its property.

Let’s take a look at how it will find a node with an example.
Let’s say I want to find the node with value 15.
First, it takes a look at the root node and finds out that 15 is less than its current value 20.
Therefore the node must exist somewhere on the left side of the root node.
It checks the node with value 10 and finds out that 15 is greater than 10.
Therefore the node must exist somewhere on the right side of the node with value 10.
Then, finally, the node with value 15 is found in the right child of the node with value 10.
Did you notice that we are eliminating half of the tree every time we compare which is very similar to binary search?
In fact, insertion and search and deletion are really the same as binary search and their performance is also the same – O(log n).

Insertion – O(log n)
Search – O(log n)
Deletion – O(log n)

Please note that the above performance is valid only if the tree is balanced which depends on the insertion order unless it balances automatically after every insertion.
In the worst-case scenario where the tree is extremely unbalanced and essentially becomes like a linked list all the operation cost will be O(n).
I won’t discuss how to balance the tree as it will be a lot of information for just one post.

Code Example

Here is the code example of binary search tree in C++

struct Tree
{
    // This could be any data type
    int val;
    
    Tree *leftChild;
    Tree *rightChild;
};

Tree *searchTree(Tree *elt, int searchVal)
{
    // value not found in the tree
    if (!elt)
    {
        return 0;
    }
    
    // found value
    if (searchVal == elt->val)
    {
        return elt;
    }
    // search value must be in one of left children nodes
    else if (searchVal < elt->val)
    {
        return searchTree(elt->leftChild, searchVal);
    }
    // search value must be in one of right children nodes
    else
    {
        return searchTree(elt->rightChild, searchVal);
    }
}

void insertTree(Tree **elt, int newVal)
{
    // found correct place to insert
    if (!*elt)
    {
        Tree *newNode = new Tree;
        newNode->val = newVal;
        newNode->leftChild = 0;
        newNode->rightChild = 0;
        *elt = newNode;
        return;
    }
    
    Tree *node = *elt;
    // new node must be inserted in one of left children
    if (newVal <= node->val)
    {
        insertTree(&node->leftChild, newVal);
    }
    // new node must be inserted in one of right children
    else
    {
        insertTree(&node->rightChild, newVal);
    }
}

// example of inorder traversal. I am just printing here
// this is called inorder traversal. 
// this will print above example tree as this.
// 8 10 15 20 21
void printInOrder(Tree *head)
{
    if (!head)
    {
        return;
    }
    
    printInOrder(head->leftChild);
    // you can do any operation here
    cout << head->val << " ";
    printInOrder(head->rightChild);
}

Conclusion

We have taken a look at binary search tree and how it maintains the order of nodes which enables fast operations such as insertion, search, and deletion.
It is a powerful data structure that has strengths of array – fast search – and linked list – flexible size adjustment.
However, the tree needs to be balanced in order to be efficient.
There is multiple tree balance logic and I will try to explain them in other posts.

Intro to Heap data structure

Posted on by NY Comdori

Heap is one of the most efficient data structure that can handle data for certain purposes.
To have a better understanding of heap you can imagine a priority queue.

For example, let’s say there are multiple jobs that you need to do for today. They could be chores, work, and any activities.
However, not all of them have the same priority and you probably want to finish jobs in order of importance.

A priority queue is a queue that takes tasks and handles them in order of specified priority.
Therefore, unlike a normal queue which is FIFO – first in first out, a priority queue always guarantees to provide an element in the order of priority.
The order could be the minimum or maximum of the priority depending on the user’s choice.

Why do I talk about the priority queue in the heap data structure post?
It’s because the heap is the most crucial part of priority queue implementation.
The heap data structure actually maintains elements based on the order specified.
Let’s take a look at how the heap is structured and how it handles data.

How is heap structured?

Typically many efficient data structures maintain elements in sorted order to access data fast.
Binary search is a good example that requires all the elements to be sorted.
Binary search tree also guarantees all the tree nodes are placed in sorted order.

However, although heap uses binary tree it is not as restrictive as the binary search tree.
The only requirement of heap is that all the children of the tree node need to be smaller than the parent. (max heap)
If a user wants min-heap then all the children of the tree node need to be bigger than the parent.
Max heap guarantees that the root of the tree will always be the largest element of all the tree nodes.
Min heap guarantees that the root of the tree will always be the smallest element of all the tree nodes.

Let’s take a look at the picture of max heap as a picture is worth a thousand words.

heap data structure

As you see the above, 98 is the largest value of all the nodes.
Then node 98 has two children, 85 and 90. Node 85 has two children 81 and 82. Node 90 has two children 84 and 88.
Please note that this tree is not strictly sorted like binary search tree.
You may have noticed that node 88, the child of 90, is greater than node 85 but it’s located at the leaf node.
Basically it is fine as long as the parent node is greater than its children.

As you can see heap condition is maintained in the above example.

  1. Node 98: 98 > 85 && 98 > 90
  2. Node 85: 85 > 81 && 85 > 82
  3. Node 90: 90 > 84 && 90 > 88

Why do we only care about parent and children relationship?
It’s because we just want to maintain everything based on priority!
What heap guarantees is that the root will be the largest value for max-heap and smallest for min-heap.

Where do you use heap for?

Now you might wonder why heap is useful when it only guarantees about the root element.
This is important because as you keep inserting elements the heap will always maintain the elements based on the priority.

Let’s go back to the very first example I gave in the beginning of the post – to dos for a day.
As you are finishing your job for the day there might be more jobs created (i.e. your family asked to pick up pizza)
The important thing is that the priority order needs to be maintained as new jobs are requested.

Therefore, heap is really the core of priority queue and priority queue works best if you want to process each element based on specified priority.

How do you maintain the heap?

The critical point of the heap is maintaining the order.
Maintenance is really simple as there are only two cases – insertion and pop of the element.

Insertion

  1. Insert the element to the leaf of the tree (I will explain which leaf in code example)
  2. Now, it is possible that heap order is broken so check and swap if the new element is greater/smaller than the parent.
  3. Recursively check until heap invariant is satisfied

This is fixing the heap upward.

Pop/Deletion

What does pop mean? You are dequeuing the root element from the heap.
After popping the root you also need to maintain the heap.

  1. Save the root element
  2. Place last element (leaf) to the root position
  3. Check and swap parent and children node until heap condition is satisfied

This is fixing the heap downward.

Array can be used to represent binary tree for the heap!

For efficient access you can use array to represent binary tree.

heap implemented based on array

Although I could use binary tree it will be less efficient since 2 children pointers are required which is less efficient since you can use the index of an array to find out the location of children.

Now, you might ask if array could be used for binary search tree.
That’s very unlikely since array is not as flexible as binary tree and it will be quite hard to maintain completely sorted order when there is constant insertion and deletion.

Code Example

This code example implemented max heap class.
I used array to represent binary tree.

#include <iostream>
#include <vector>
using namespace std;

class MaxHeap
{
    int lastIdx;
    int queueSize;
    vector<int> queue;
    
public:
    
    MaxHeap(int _queueSize) 
        : lastIdx(-1), 
          queueSize(_queueSize), 
          queue(_queueSize) {}
    
    bool insert(int val)
    {
        if (lastIdx >= queueSize)
        {
            return false;    
        }
        
        // insert the element to the last leaf node of queue 
        // and fix the heap upward
        ++lastIdx;
        queue[lastIdx] = val;
        
        fixHeapUpward(lastIdx);
        
        return true;
    }
    
    int max()
    {
        if (lastIdx == -1)
        {
            throw std::runtime_error("Extracting from empty queue not allowed");
        }
        
        return queue[0];
    }
    
    void pop()
    {
        if (lastIdx == -1)
        {
            return;
        }
        
        // get max value of the heap
        int result = queue[0];
        
        // now root is empty and get last element and fix heap downward
        queue[0] = queue[lastIdx--];
        fixHeapDownward(0);
        
        return result;
    }
    
    void print()
    {
        for (unsigned int i = 0; i < queue.size(); ++i)
        {
            cout << queue[i] << " ";
        }
        cout << endl;
    }
    
private:
    int findParentIdx(int idx)
    {
        if (!idx)
        {
            // this is root index
            return 0;
        }

        if (idx % 2)
        {
            // this must be left, 2 * h + 1
            return idx / 2;
        }
        else
        {
            // this must be right, 2 * h + 2
            return (idx - 2) / 2;
        }
    }
    
    void fixHeapUpward(int idx)
    {
        int parentIdx = findParentIdx(idx);
        if (queue[parentIdx] < queue[idx])
        {
            swap(queue[parentIdx], queue[idx]);
            fixHeapUpward(parentIdx);
        }
    }
    
    void fixHeapDownward(int idx)
    {
        int maxIdx = idx;
        for (int childIdx = idx * 2 + 1; 
             childIdx <= idx * 2 + 2 && childIdx <= lastIdx; 
             ++childIdx)
        {
            if (queue[childIdx] > queue[maxIdx])
            {
                maxIdx = childIdx;
            }    
        }
        
        if (maxIdx != idx)
        {
            swap(queue[maxIdx], queue[idx]);
            fixHeapDownward(maxIdx);
        }
    }
};

int main() 
{
    // heap size 10	
	MaxHeap heap(10);
	
    heap.insert(81);
    heap.insert(85);
    heap.insert(82);
    heap.insert(98);
    heap.insert(84);
    heap.insert(90);
    heap.insert(88);
	
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();
	cout << heap.max() << endl;
	heap.pop();

	return 0;
}

Performance

Insertion: O(log n)
Pop: O(log n)
Making heap: O(n log n)

Conclusion

We have taken a look at heap data structure.
Although it might be slightly hard to fully understand heap it is not really complicated data structure once you understand the purpose and how it fulfills it.
In fact, heap could be used to solve quite a bit of real-world problems pretty nicely.
Please let me know if you have any questions or suggestions and good luck!

Intro to Array data structure Part 2 – 2D Array

Posted on by NY Comdori

Continuing from the last post I am going to discuss more about the array data structure which is 2D array.
In this post, I will focus on the basic concept and usage.

What is 2D Array?

2D array is basically array within array.
Typically array contains specified data type in its element.
However, it is possible that the element can contain another array instead!

This is a 2D array with 3 rows and 5 columns.
In each row, there is an array of size 5 which is the column size.
In other words, there is an array of size 3 (row) and there is another array size 5 within each element.

Code Example

Here is a code example of usage of the 2D array.

This is a basic access usage example.

#include <iostream>

using namespace std;

int main()
{
    // declaration of 2D array without initializing elements
    int two_d_arr[3][5];
    
    // you can also initialize 2D array just like 1D array
    // you just need to make sure there is an array for each element.
    // 3 rows. Each row contains an array of size 5
    int two_d_arr2[3][5] = {{10, 15, 23, 31, 3}, {13, 72, 29, 19, 85}, {61, 42, 1, 5, 27}};
    
    // when initializing 2D array you don't need to specify row size
    // compiler will figure out row size for you as long as correct column size is provided
    // int two_d_arr2[][5] = {{10, 15, 23, 31, 3}, {13, 72, 29, 19, 85}, {61, 42, 1, 5, 27}};
    
    // you can use for loop to access 2D array
    // this will print out each column per row first
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            // first bracket [i] represents row index
            // second bracket [j] represents column index
            cout << two_d_arr2[i][j] << " ";
        }
        
        cout << endl;
    }
    cout << endl;
    
    /*
     * output
     * 10 15 23 31 3
     * 13 72 29 19 85
     * 61 42 1  5  27
     */
    
    // or you can switch row and column if you want
    // this will print out each row per column first
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            // first bracket [i] represents row index
            // second bracket [j] represents column index
            cout << two_d_arr2[j][i] << " ";
        }
        
        cout << endl;
    }
    
    /*
     * output
     * 10 13 61
     * 15 72 42
     * 23 29 1
     * 31 19 5
     * 3  85 27
     */
    
    return 0;
}

Accessing 2D array is really like 1D array except you need to specify row and column index.

Here is another code example that 2D array is used as a function parameter.

#include <iostream>

using namespace std;

// array parameter needs to know column size. 
// but row size is still necessary as another parameter in order to loop it
void printArray(int arr[][5], int rowSize)
{
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            cout << arr[i][j] <<  " ";
        }
        
        cout << endl;
    }
}

int main()
{
    int two_d_arr2[][5] = {{10, 15, 23, 31, 3}, {13, 72, 29, 19, 85}, {61, 42, 1, 5, 27}};
    
    printArray(two_d_arr2, 3);
    return 0;
}

Overall, it’s fairly simple to use 2D array that we just need to provide row and column index accordingly.
Sometimes you can skip row index when declaring 2D array with initialization or using as a function parameter.

Please note that you can have 3D array or more!
You just need to have a proper index when you access them.

Conclusion

We have taken a look at the basics of array data structure.
However, there are still more topics to discuss about array!
I will try to have another post about it.
You might also want to take a look at my post about linked list so you can have apple to apple comparison.

Intro to Array data structure Part 1

Posted on by NY Comdori

Today, we will go over a popular data structure – array.
This is the most basic and fundamental data structure in computer science regardless of any programming language.
Even many complex data structures use array inside the implementation.
Programming language like python doesn’t have array but it provides list instead. (of course, python list is much more flexible and easier to use than C++ array)
In this post, I will go over some important characteristics of array with example code based on C++.

What is Array?

Array is a contiguous piece of memory of a certain data type.
It sounds hard but it will be very clear once you see this picture and example code.

Here, this picture is an array of integer with size 3.

array

Data type is an integer and there are a total of three elements for the array.
Please note that all those three elements are located right next to each other.

The first element of the array contains the integer 10 and 3 for second and 99 for third respectively.
In order to access each element, we need to know the index of the element.
This could be a little counter-intuitive but index of C++ always starts from 0 for array.

For example, if you would like to access the first element you need to know that it’s located at index 0.

Let’s take a look at the C++ code example for array declaration and basic usage.

#include <iostream>

using namespace std;

int main()
{
    //this is just a normal integer variable
    int temp;
    
    // this is an array of integer with size 3
    // please note that [ ] is necessary in order to declare it as an array.
    // you need to provide size inside [ ] unless you are initializing right away.
    // however, if you are initializing the array like below compilre can figure out the size.
    int arr[] = {10, 3, 99};
    
    // 3 inside [ ] means size of the array and it is necessary if you are not initializing like above
    // int arr[3]; 
    
    // you can access each element in the array using index
    // you will see 10 in the screen
    cout << "value of first index of the array:" << arr[0] << endl;
    
    // you can also assign a value to each element using index
    // you will see 11 on the screen
    arr[0] = 11;
    cout << "value of first index of the array after change:" << arr[0] << endl;
    
    // you will see 3 on the screen
    cout << "value of second index of the array:" << arr[1] << endl;
    
    // in this case, arr can only hold int because it's declared as int arr[3]!
    // this will cause a compilation error!
    // arr[2] = "test";
    
    // implicit conversion from 1.1 to 1. bad!
    // double precision will be dropped!
    // you will see 1 on the screen if you print arr[2]
    // arr[2] = 1.1;
    
    return 0;
}

As you see above, an array is merely a container that can hold many elements of the same data type.
You can have an array of double, short, int or string. (Please note that string is already an array of char)

One thing you have to remember is that unlike python an array in C++ can contain only a single data type.
Another words, if you have an array of int, then it can only hold int.
Although you can still assign double, short or any other number related data type it doesn’t necessarily mean it’s correct.

What happens you mistakenly assign 1.1 to arr[2] like the above example?
It will implicitly convert 1.1 to 1 because int cannot take double precision and will only take the integer part.
And the user might be surprised to see 1 on the screen instead of 1.1!

Array access with loop

You can use a loop (for, while or do-while) to access an array efficiently and elegantly.
And I will explain it using the example below.

Let’s say you are to write a program that does the following.
1. Take 5 test scores from the user
2. Find the lowest and highest test score
3. Calculate the average of those scores
4. Print the average, lowest and highest score along with individual test scores.

#include <iostream>

using namespace std;

int main()
{
    const int NUM_TESTS = 5;
    int scores[NUM_TESTS];
    
    for (int i = 0; i < NUM_TESTS; ++i)
    {
        cout << "Please enter a test score:";
        
        // you can use for loop to access each element in the array!
        // value of i will be from 0 to NUM_TESTS - 1 which are 0,1,2,3,4
        // please note that the index of the array always starts from 0!
        cin >> scores[i];
    }

    // in order to find lowest score you need to compare all the element
    // starting from the element at index 0
    // so far the element at index 0 is the lowest test score.
    int lowestScore = scores[0];
    
    // please note that this loop starts at index 1 since you already got the element at index 0
    // i will be 1,2,3,4
    for (int i = 1; i < NUM_TESTS; ++i)
    {
        // update lowestScore if current element is lower
        if (scores[i] < lowestScore)
        {
            lowestScore = scores[i];
        }
    }
    
    cout << "The lowest score is " << lowestScore << endl;
    
    // please refer to explantions for lowest score as this is very similar
    int highestScore = scores[0];
    for (int i = 1; i < NUM_TESTS; ++i)
    {
        if (scores[i] > highestScore)
        {
            highestScore = scores[i];
        }
    }
    
    cout << "The highest score is " << highestScore << endl;
    
    int total = 0;
    for (int i = 0; i < NUM_TESTS; ++i)
    {
        total += scores[i];
    }
    
    double avg = total * 1.0 / NUM_TESTS;
    cout << "Average of test scores:" << avg << endl;
    
    for (int i = 0; i < NUM_TESTS; ++i)
    {
        cout << scores[i] << " ";
    }
    cout << endl;
    
    return 0;
}

As you can see above it’s much easier to access (read/write) the array using loops and that’s usually recommended way unless you want to access some specific location.

Array as a function parameter

In the above example, we observed that you can have a variable for the array.
Then you might ask if the array can be used in function, either as a parameter or return type.


Quick answer is that a function can take an array as a parameter but it cannot return the array.
However, it doesn’t mean returning an array is completely impossible. Instead of returning array directly, it can return a pointer which is essentially the same as array.
Although a pointer to an array and an array is not exactly the same it is still possible to use pointer like an array.
I will discuss the difference between array and pointer in another post.
For now, let’s just focus on array used as a function parameter.
I rewrote above example code using functions instead.

#include <iostream>

using namespace std;

// this is basic syntax to have an array parameter
// you only need to specify the parameter is array. don't need to have size inside [ ]
int getHigestTestScore(int scores[], int size)
{
    // -999 is just a custom error code
    if (size <= 0)
    {
        return -999;
    }
    int highestScore = scores[0];
    for (int i = 1; i < size; ++i)
    {
        if (scores[i] > highestScore)
        {
            highestScore = scores[i];
        }
    }
    
    return highestScore;
}

// you could also specify the size like below and it works fine.
// but it's quite rigid and usually not a good choice
// in the end this function really assumes the array is sizes of 5 which isn't flexible
// and it involves some hard coded number which smells
int getHigestTestScore2(int scores[5])
{
    int highestScore = scores[0];
    for (int i = 1; i < 5; ++i)
    {
        if (scores[i] > highestScore)
        {
            highestScore = scores[i];
        }
    }
    
    return highestScore;
}

int main()
{
    int arr[] = {1,2,3,4,5};
    int high1 = getHigestTestScore(arr);
    
    int high2 = getHigestTestScore2(arr);
    return 0;
}

I think the example code is pretty clear on how to use array as a function parameter.
Although you can use a pointer instead of array I omitted here to just focus on array only.

Pros

  • Random access is allowed which enables fast search
  • No extra space is required like Linked List (i.e., next pointers)
  • Memory locality yields better access performance than Linked List since all the elements are all located next to each other

Cons

  • Adjusting the size is not flexible. You will need to copy/move elements after increasing/decreasing the size.
  • Insertion and deletion of elements are quite expensive because you have to copy/move all the elements after the operations.

Performance

Search – O(1)
Insertion – O(n)
Deletion – O(n)

Conclusion

We have taken a look at basic concepts and usage of array. However, this is not it!
There are many array related topics such as 2D array and array pointer I am going to discuss in next post.

Intro to Linked List data structure

Posted on by NY Comdori

Today, we will go over a popular data structure – linked list.
Linked list may not make much sense for some languages such as python and javascript since there is already a good one such as list.
However, since linked list is quite useful for languages like C++ it is still worthwhile to go over.
In this post I will go over some important characteristics about linked list and strengths and weaknesses.
Please note that all the explanations will be based on C++.

What is Linked List?

Linked list is a data structure that each node is connected like a chain via pointer.
It is one of fundamental data structure in C++ and widely used in C++ standard library (STL).

I believe a picture is worth a thousand words and let’s take a look at how a linked list looks like before any explanations.

As you see above there are three nodes in the linked list.
Each node is based on Node struct as below which contains a value and a pointer to the next Node.

struct Node
{
    // value that this Node contains. 
    // It could be any data type you want to contain
    int   val;
    
    // pointer to next node
    Node *next;
    
    // pointer to previous node.
    // this is optional
    // Node *prev;
};

The example code has only one pointer ‘next’ but you can also have another Node * to point to the previous Node.
If you have only one pointer (likely it’s a pointer to the next Node) it’s called a singly linked list.
If you have two pointers one pointing to the next and the other to the previous then it’s called a doubly linked list.

Linked List Operations – insert, search, delete

As you can imagine there are three basic operations for a linked list.
You need to be able to search a node in the list, insert and delete.
Let’s go over each operation.

Search

How should the search be?
Given you have a value to search you need to start from the head of the list and check if each node in a chain is the same as the search value.
Return a pointer to the node if you find it or null pointer otherwise.
Let’s take a look at code example for search.

/**
 * @brief  search a node based on search value
 * 
 * @param  head       head of linked list
 * @param  searchVal  value to search in the list
 * 
 * @return pointer to found node. null otherwise
 */
Node *searchNode(Node *head, int searchVal)
{
    // end of the list. value not found
    if (!head)
    {
        return 0;
    }

    if (head->val == serachVal)
    {
        return head;
    }
    else
    {
        return searchNode(head->next, searchVal);
    }
}

I implemented the operation recursively so I don’t need to write a loop. (I thought the recursive solution was easier than loop but it’s your choice)
I actually also used loop based implementation for insertion operation for your reference.

Insertion

Inserting a node could be slightly trickier depending on how you want to maintain the list.
There are three possible cases for insertion.

1. Insert the node at the head of the list
This one is the easiest as you just need to create a node and insert the node.
Here is the code example for head insertion.

/**
 * @brief  node insertion at the beginning of the list
 * 
 * @param  head    double pointer to head since you need to update 'head' after insertion
 * @param  newVal  new value to insertNode
 */
void insertNode(Node **head, int newVal)
{
    Node *newNode = new Node;
    newNode->val = newVal;
    newNode->next = *head;

    // update head
    *head = newNode;
}

2. Insert the node at the tail of the list
This one is slightly harder than head insertion but still pretty simple.
What you need to do is to traverse to the end of the list and insert the node there.

/**
 * @brief  node insertion at the end of the list
 * 
 * @param  head    double pointer to head since you still might need to update 'head'
 *                 if the list is empty
 * @param  newVal  new value to insert
 */
void insertNode(Node **head, int newVal)
{
    Node *newNode = new Node;
    newNode->val = newVal;
    newNode->next = 0;

    Node *tailNode = *head;
    while (tailNode && tailNode->next)
    {
        tailNode = tailNode->next;
    }

    if (!tailNode)
    {
        *head = newNode;
    }
    else
    {
        tailNode->next = newNode;
    }
}

3. Insert the node based on the sorted order of the list.
Imagine you want to maintain the list in sorted order (decreasing or increasing).
Then you will need to find a proper location to insert.

For example, let’s say you have a list like below and you would like to insert value 4.
1-> 3-> 5

Then you need to traverse the list and find a node that is not less than 4 which is 5, the last one, and create a node and insert.
However, there is a couple of other edge cases such as the inserting position happens to be at the head or tail of the list.
Although this one is not terribly difficult it does require little more thoughts than the others.

void insertNode(Node **head, int newVal)
{
    // create new Node
    Node *newNode = new Node;
    newNode->val = newVal;
    newNode->next = 0;
    
    // if empty list then just insert it here
    if (!*head)
    {
        *head = newNode;
        return;
    }
    // check if it needs to be inserted at head.
    else if (newNode->val < (*head)->val)
    {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    Node *iter = *head;
    
    // loop until you find first Node that is not less than new value
    while (iter && iter->next)
    {
        if (iter->next->val >= newNode->val)
        {
            break;
        }
        
        iter = iter->next;
    }
    
    if (iter->next)
    {
        newNode->next = iter->next;
    }
    
    iter->next = newNode;
}

The tricky part of insertion is that you have to make sure you update the next pointers properly.
1. If insertion is happening at the head, make sure head pointer is updated and the next pointer of new node point to last head
2. If insertion is happening at the tail, make sure the last node of the list is pointing to the new node properly
3. If insertion is happening in the middle of the list, make sure the previous node’s next points to new node and new node points to the proper next one.

deletion

The deletion of a node is a very similar process as insertion.
First, you need to find which node to delete if there is any and properly updates the next pointers.
Just like insertion deleting node could be the head, the tail or in the middle of the list.
Let’s take a look at the code example.

/**
 * @brief  delete a node from the list if there is one
 *         for simplicity I don't delete all the duplicate values here
 * 
 * @param  head       double pointer to head in case you have to delete head node
 * @param  deleteVal  value to delete
 */
void deleteNode(Node **head, int deleteVal)
{
    Node *iter = *head;
    
    // nothing to delete
    if (!*head)
    {
        return;
    }
    // deleting head. need to update head
    else if ((*head)->val == deleteVal)
    {
        *head = (*head)->next;
        delete iter;
        return;
    }

    while (iter && iter->next)
    {
        if (iter->next->val == deleteVal)
        {
            break;
        }

        iter = iter->next;
    }

    if (iter->next)
    {
        Node *delNode = iter->next;
        iter->next = iter->next->next;
        delete delNode;
    }
}

Pros

  • Unlike an array size of a linked list is very flexible as long as the memory permits
  • Insertion and deletion are much simpler than an array. For an array insertion/deletion you have to move many other elements after the operation
  • It is a perfect data structure to implement more complex data structures like Stack and Queue since you only need to maintain head(or tail) of the list for insertion, search, deletion

Cons

  • It requires extra memory (next, prev pointers)
  • It does not allow random access like an array and therefore search could be slower than an array

Performance

Search – O(n)
Insertion – O(1) if always insert at the head (for cases like Stack)
O(n) otherwise
Deletion – O(1) if always delete head (for cases like Stack)
O(n) otherwise

Conclusion

We have taken a look at some basics of linked list.
Linked list is a great data structure for some special purposes due to its flexibility of insertion and deletion.
However, there are some weaknesses about it so it requires some discretion to wisely use it.

Thank you for reading my post and please let me know if you have any questions or suggestions and good luck!