About Disjoint-Set Forests

Disjoint-Set Forests is very useful to solve the problems such as connected component in a graph. For example,  we have several set {a, b, c}, {d, e}, {f}. The elements in set is vertices that connected to each other. If we have an edge e(b,f), then we can merge the set {a,b,c} and {f} since now they are connected.

The common operations in disjoint-set are Make-Set, Union and Find-Set. Here Union is the operation that merge two sets and Find-set is that given a element, find out which set this element is in. To model the disjoint-set problem. We can use a forest such that each tree is a set. The representative of a set is the root of that tree. And each element in the tree has a parent pointer. If we want to do Union, we can just put one tree as the sub tree of another. If we want to do Find-Set, we just start from that element and follow its parent pointer until we reach an element whose parent is itself.

However, to make the operations efficiently, two optimization can be made:

1. Union by rank: In order to keep Find-Set efficient, we need to keep the depth of the tree small. In order to do that, for each tree, we can maintain a rank which stands for the largest depth of the tree. When we Union two trees, we make the tree with smaller rank as the subtree of the tree with bigger rank. Basically, we made the the parent pointer of the root of the smaller ranked tree to point to the root of the bigger ranked tree.
2. Path compression: Still we want to further improve Find-Set, the idea is after we do a Find-Set, actually we had a path from root to the query element. Then we can modify all the element in this path to point their parent pointer to the root, which will shorten the path for future query.

Implement Text Editor with Gap Buffer

Gap Buffer is a data structure which can be used to implement text editor. The advantage is that insertion/deletion can be very efficient and the data structure is simple. The disadvantage is when cursor changes its location frequently or the gap is frequently full, there will be a lot of copying operation, which is costly. The following gives more details about gap buffer.

• Basically gap buffer can be implemented as an array (or a dynamic array) with some pointers to differentiate three regions: the segment before the gap, the gap, the segment after the gap.

| the front segment  |   the gap  |  the back segment  |

• The location of the cursor in the text editor decides the border between the front segment and the gap. A example is given here:

We had a [            ] big day

• As the above example, "We had a" is the front segment, "[   ]" is the gap buffer and "big day" is in the back segment. 
• When insertion, new text is filled in the gap buffer, the start pointer of the gap buffer also moves accordingly. If the gap is full, we need to create new gap buffer and we may also need to move all the content in the back segment backwards.
• When deletion,  we only need to move the start pointer of the gap buffer forwards if we are deleting the text in the front segment or  the end pointer of the gap buffer backwards if we are deleting the text in the back segment.
• If we move the cursor, for example, the cursor is between "We" and "had" now:  "We [     ] had a big day". We need to copy the "had a" which was originally in the front segment to the back segment.

The Comparison between BST, Hashtable, Array and Linked List

BST:

• locating/deleting/inserting an element is not slow -- O(logn)
• maintain the order between elements
• support range query 
• if not balanced, the worst case is like a linked list

Hashtable:

• look up operation is fast: O(1) if the hash function is well chosen.
• have space overhead
• don't support range query

Array:

• allow random access
• can explore cache locality
• updating is costly

Linked List:

• allow easy insertion/deletion
• do not support random access
• may not have cache locality

Binary Heap

Binary Heap is an important data structure which can be used to implement priority queue. Two types of binary heap are commonly seen: min-heap and max-heap. A binary heap has two properties:

• Shape property: the heap should be a full binary tree (can be denoted as an array)
• heap property: children should be smaller (bigger) than parent

When inserting an element into heap, we insert from bottom (leaf). Then we check if the two properties hold, otherwise we swap parent and child. When removing an element from heap (always from root), we use the last element at the last level to replace root, then we adjust heap. So,

• The time complexity of insertion is O(logN)
• The time complexity of removal is O(logN)
• The time complexity of building a heap can be O(N)

With binary heap, a K-way merge can be done in O(N*logK), naive ways take O(N*K). Besides, we also have min-max heap which can insert remove the min and max element in O(logN). Basically, it is a mixed heap with odd level to be min heap and even level to be max heap.