Array Implementation of OrderedSet
- Implement the core operations of OrderedSet efficiently (array base).
We want to efficiently implement the OrderedSet ADT with an array as the underlying data structure.
Exercise Complete the following table.
| Operation | How? | Runtime |
|---|---|---|
has | ||
insert | ||
remove | ||
size |
Solution
Except for size, all operations require a helper find method to check if an element exists. Then, we can perform Binary Search, so find and has will cost $\Omicron(\lg n)$. The insert and remove operations will remain linear since we must shift the elements around to keep the values in order.
| Operation | How? | Runtime |
|---|---|---|
has | return find(t) != -1; | $\Omicron(\lg n)$ |
insert | Find where to insert, then shift elements to make room. | $\Omicron(n)$ |
remove | Find the element, shift all element after it to left. | $\Omicron(n)$ |
size | return numElements; | $\Omicron(1)$ |
find | Binary search | $\Omicron(\lg n)$ |
We leave this as an (unsolved) exercise to you: implement the operations of an array-based OrderedSet.