Data Structures

Theory - Data Structure Classification

Lesson

This post is optional reading, but is interesting, and helped DeriveIt's creators view data structures more clearly.

As you've learned about the different data structures, you've probably picked up on the idea that some data structures are slower than others. For example, Arrays and LinkedLists take more time to read/delete than Sets in some cases. Why is this the case?

Well, the slower data structures store more information! There's maintenance cost to upkeeping that extra information that they store.

In the case of an ordered data structure (like an Array or LinkedList), where elements have an index between 0 and N, if we add or delete an element at index i, we must shift over N - i + 1 elements to maintain the indexes properly. That gives us an O(n)O(n) cost to maintain ordered (indexed) data structures.

For Arrays, LinkedLists, and any other indexed data structures:

Maintenance Cost=O(n)\notag \text{Maintenance Cost} = O(n)

We have a choice of when we do the maintenance! We can do it right when we edit the data structure, like in the case of the array where we shift everything over immediately. For the array, time_read=O(1)\text{time\_read}=O(1) yet time_write=O(n)\text{time\_write}=O(n). Or, we can do it right when we read from the data structure, like with the LinkedList, where time_read=O(n)\text{time\_read}=O(n) (we walk along the LinkedList, effectively reconstructing the index lazily) yet time_write=O(1)\text{time\_write}=O(1).

The point is that we eventually need to do an O(n)O(n) operation if we edit an indexed data structure. It doesn't matter if it's an Array, or a LinkedList, or some other creative indexed data structure we invented. If we want to store "indexed" information, that's a fundamental cost we must face!

There is a formula that describes this idea: time_read+time_write=Maintenance Cost\text{time\_read} + \text{time\_write} = \text{Maintenance Cost}. This is a lot like a conservation of energy equation, and it holds for every data structure.

In general, the maintenance cost is determined by the information you want to store. It equals it equals the number of affectancies (items you might affect by making a change). It can often be computed before you even know what your data structure looks like! This is a powerful statement because it lets you make a sweeping statement about entire classes of data structures.

Now we're ready to talk about other data structures. Let's start with Sets, which are easy. For Sets and other unordered data structures, elements have no effect on each other the way they did in an Array (due to the index invariant). This means:

For Sets, HashMaps, and any other completely unordered data structures:

Maintenance Cost=O(1)\notag \text{Maintenance Cost} = O(1)

Finally, the last major data structure is a "sorted" or "ranked" data structure. This sits in-between an Array and a Set; it cannot be arbitrarily ordered like an Array, but is also not disordered like a Set. The sorting lower bound for nn items is O(nlog⁡n)O(n \log n), which means the maintenance cost of one item is on aggregate log⁡n\log n.

Worth mentioning as a side-note that Maintenance Cost≥build_timen\text{Maintenance Cost} \ge \frac{\text{build\_time}}{n}.

For BSTs, B-Trees, Sorted Arrays, and any other sorted data structures:

Maintenance Cost=O(log⁡n)\notag \text{Maintenance Cost} = O(\log n)

These are simply lower bounds. They are like speed limits; they are the best you can do, but of course, you can do worse than them. For example, a Sorted Array has O(n)O(n) insert time despite O(log⁡n)O(\log n) being its lower bound maintenance cost.

Data Structure classification

Now we're going to break down many different data structures into classes, based on the information they store. We'll go into more depth than above, introducing subclasses like Stacks and Queues (simply lumped into ordered above). We'll do aggregate analysis in cases where the results are unaffected (wrapping all equations in a big O instead of using exact values).

Each new type of information will be written with an inline code block like type.

Note that data structures can always be combined at the cost of taking the larger of the two Maintenance Cost\text{Maintenance Cost} values. (eg if you store elements in both an Array and a Set for fast value lookups).

Ordered Data Structures

i = ability to look up any index.

Surprisingly, this is log⁡n\log n, (it's not nn). Although, you can usually think of it as nn, since the log⁡n\log n case is very rare, and comes with extra overhead.

Maintenance Cost=O(log⁡n)\notag \text{Maintenance Cost} = O(\log n)
Open SpoilerClose Spoiler

BST:

You can store all your items in a self-balancing BST, where each node knows the number of nodes below it (this is called an "order statistic tree"). The position is the index, and it has the log⁡n\log n behavior of a BST. However, this is relatively rare.

O(log⁡n)O(\log n) read i

O(log⁡n)O(\log n) write i

Array:

O(1)O(1) read i

O(n)O(n) write i

LinkedList:

O(n)O(n) read i

O(n)O(n) write i

O(1)O(1) write i once we read i

Lazy Array:

O(n⋅w)O( n \cdot w ) read i

O(1)O(1) write i

1i = ability to look up a single index, like the last element.

Maintenance Cost=O(1)\notag \text{Maintenance Cost} = O(1)
Open SpoilerClose Spoiler

Stack:

O(1)O(1) read i=n

O(1)O(1) write i=n

Queue (Doubly Linked):

O(1)O(1) read i=0,n

O(1)O(1) write i=0,n

Specific Index Array:

O(1)O(1) read i=L

O(1)O(1) write i=L

Unordered Data Structures

v = ability to look up a single value.

Maintenance Cost=O(1)\notag \text{Maintenance Cost} = O(1)
Open SpoilerClose Spoiler

Set:

O(1)O(1) read v

O(1)O(1) write v

HashMap:

O(1)O(1) read v

O(1)O(1) write v

Sorted Data Structures

k = ability to look up any kth smallest/largest element.

Maintenance Cost=O(log⁡n)\notag \text{Maintenance Cost} = O(\log n)
Open SpoilerClose Spoiler

BST:

O(log⁡n)O(\log n) read k

O(log⁡n)O(\log n) add/remove

O(nlog⁡n)O(n \log n) build

1k = ability to look up a specific kth smallest/largest element .

Notably, build cost is O(n)O(n), not O(n⋅Maintenance Cost)O(n \cdot \text{Maintenance Cost}). In general the optimal time it takes to build a data structure is at most O(n⋅Maintenance Cost)O(n \cdot \text{Maintenance Cost}), but it can be less.

Maintenance Cost=O(log⁡n)\notag \text{Maintenance Cost} = O(\log n)
Open SpoilerClose Spoiler

Heap:

O(1)O(1) read k=0

O(log⁡n)O(\log n) add/remove

O(n)O(n) build, notably not O(n log n).

Lookup Median:

O(1)O(1) read k=n/2

O(log⁡n)O(\log n) add/remove

O(n)O(n) build

Lookup fixed k=L:

O(1)O(1) read k=L

O(log⁡n)O(\log n) add/remove

O(n)O(n) build

Sliding Window Data Structures

In this kind of data structure, elements can be added or removed from the stream at any time.

We can predict the costs here by figuring out the normal cost of finding the value, and dividing by nn.

sum-window = ability to look up the sum of the window.

Maintenance Cost=O(1)\notag \text{Maintenance Cost} = O(1)
Open SpoilerClose Spoiler

Computing a sum costs O(n)O(n), and dividing by nn we get O(1)O(1).

Indeed this is true; this is a trivial sliding window algorithm.

median-window = ability to look up the median of the window.

Maintenance Cost=O(log⁡n)\notag \text{Maintenance Cost} = O(\log n)
Open SpoilerClose Spoiler

Computing a median k value has Maintenance Cost\text{Maintenance Cost} O(log⁡n)O(\log n), and dividing by nn we get O(log⁡n)O(\log n).

This is indeed the complexity we get in the hourglass heap solution to Sliding Window Median! It just requires a heap deletion operation in log⁡n\log n time which is relatively easy to do, although not usually built into Heaps (usually they lazily delete elements when they read, which doesn't work here).

max-window = ability to look up the max value in the window.

Maintenance Cost=O(1)\notag \text{Maintenance Cost} = O(1)
Open SpoilerClose Spoiler

Finding a maximum over nn elements takes O(n)O(n), so dividing by nn we get O(1)O(1).

This is somewhat surprising! But it is indeed the solution we find with the monotonic queue solution to Sliding Window Max!

String Data Structures

Prefix problems:

prefix-simple = ability to check for a string prefix of a fixed string.

This is a trivial problem because it only involves 1 string; it's just here so you can see we can multiply out the per-element cost to the other problems and get Tries etc.

Maintenance Cost=O(m)\notag \text{Maintenance Cost} = O(m)
Open SpoilerClose Spoiler

To swap out the string with another string, we need to replace mm characters.

Notice that this gives O(1)O(1) maintenance per character.

prefix = ability to check for a string prefix of any of the given strings in a set.

Maintenance Cost=O(m)\notag \text{Maintenance Cost} = O(m)
Open SpoilerClose Spoiler

This is the typical Trie solution.

We can multiply out the O(1) Maintenance Cost per character to get this cost.

Substring problems:

Notice the prefix problem can be turned into the substring problem by simply framing it as a Sliding Window version of the same problem. The maintenance cost per element is 1 for prefixes, so it should also be 1 for substrings, and we'd expect O(m)O(m) per element for substrings. This is indeed what you get - KMP and Aho Corasick data structures.

substring-simple = ability to check for a substring of a fixed string.

Maintenance Cost=O(m)\notag \text{Maintenance Cost} = O(m)
Open SpoilerClose Spoiler

If we assume O(1)O(1) cost per character, we get O(m)O(m) here. This is the KMP solution!

substring = ability to check for a substring of any of the given strings in a set.

Maintenance Cost=O(nk)\notag \text{Maintenance Cost} = O(n k)
Open SpoilerClose Spoiler

If we assume O(1)O(1) cost per character, we get O(k)O(k) here per avg string comparison, times the nn strings. This is essentially O(m)O(m) like in the other problems, but aggregated over multiple strings.

This is the Aho Corasick solution!

Union Find Data Structures

disjoint-set = ability to lookup if two elements are in the same set.

This includes ability to merge sets, otherwise this would be trivial. A naive solution puts the maintenance cost at O(n)O(n). However, if you apply a few heuristics, you can get this to O(α(n))O(\alpha(n)) - this is known as the Union Find data structure.

The Soft Heap does slightly better on a few of the operations, but is still bounded by this maintenance cost.

Maintenance Cost=O(α(n))\notag \text{Maintenance Cost} = O(\alpha(n))
Open SpoilerClose Spoiler

Disjoint Set / Union Find

create set O(1)O(1)

merge sets O(α(n))O(\alpha(n))

add element O(α(n))O(\alpha(n))

check membership O(α(n))O(\alpha(n))

Soft Heap

create set O(1)O(1)

merge sets O(1)O(1)

add element O(log⁡1/ϵ)O(\log 1/\epsilon)

check membership (really, find-min) O(1)O(1)

Mark as Completed:
Submits:
test
Test your code to get an output here!
test(
)
Test your code to get an output here!