An actual binary search on a linked list???

During my last data structures lecture, our professor was talking about priority queues, selection and insertion sorts. And he mentioned, as a non-examable material, how we might achieve a faster insertion when considering a sorted sequence-based priority queueue.

Sequence-based priority queue on a sorted list

Considering the interface of a priority queue, we need to implement three main methods:

• push(T x) for inserting a new element into the priority queue,
• top() for getting the minimum element, and
• pop() for removing the minimum element from the priority queue.

We note that the last two methods could also be implemented as one: removeMin() which in addition to removing the minimum element, it also returns it. What's more, the implementation details what we mean by a "sequence-based priority queue on a sorted list". Specifically, the implementation for this data structure would be to store elements inside the priority queue (as the elements are pushed) as a sorted list, so that top() and pop() would be $O(1)$ in time complexity.

A naïve approach to this would be to, as inserting into the priority queue, going through the entire list and finding where that element belongs. Consider the example below, when we're adding 52 to the sorted list, we need to compare 52 with all of the numbers in the priority queue: 7, 9, 13, and 21. This means that an insertion would take $O(n)$ time.

What's unlucky is, if we were to implement a sorting algorithm from this, we would get $O(n^2)$ time complexity, due to the insertion taking too long. How do we improve this?

Ohhh, right... Let's binary search, then. Not so fast.

My first thought to this problem was to just binary search the elements already inside the priority queue. We already know that the list is sorted, so we could just search the elements in $O(\log n)$ time. The tricky thing is we want to insert into the list, and the list is stored as a continuous array, meaning that, even if we were to find the index we want to insert in $O(\log n)$ time, we still need to copy over the elements to hold the structure of the array — it still has to be continuous in memory — which would take $O(n)$ time. So... We aren't so fast after all.

Okay, so we need to find a way to insert quite quickly in a list... And it hit me: the answer is linked list. If we were to store the elements as a linked list, when we find the location of the insertion, adding the element is as simple as changing the head pointers. But, how do we find where to insert the element. It's not like we can binary search a linked list — spoilers...

Space-time trade off

Well, the current data structure only uses $O(n)$ memory — just for storing the list — so could we use some more memory to get a lower time complexity? Let's try storing the partial solutions somewhere as we insert into the priority queue, just to avoid some recalculations. We once more consider the example given above. From the elements already inside the priority queue, we had already calculated that $21 > 7, 9, 13$. When 52 came in, we should probably directly compare 52 with 21, without comparing with all of the other numbers.

Let's try thinking about this with a linked list. We say we want to insert 19 to the linked list:

For this case, we would compare with 7, 9, 13, and 21. When we see that $19 < 21$, we would put 19 in between 13 and 21. As expected this takes $O(n)$ time, only if there was a faster way to do this by skipping some nodes in the linked list. What if we had something like:

This would allow us to compare with 7, use the express lane to 13, compare with 13, and finally compare with 21. If we had this in a large list with optimally placed express lanes, this could save tremendous amounts of time. More formally, we would have something like:

With this kind of linked list, if we were to add 32, we would insert it as:

This just takes three comparisons, instead of the usual seven. This seems like a good start, but how do we construct this linked list? How do we know where to put these express lanes? I mean, it seems quite arbitrary...

Some formalism

This data structure is called a skip list or a skip linked list, since we have these express lanes to skip over some elements.

For ease of implementation, we need to add a sentinal or head node to the beginning of the skip list. This allows us to easily add to or remove from the start of the skip list.

Furthermore, when we think of skip lists conceptually, we see that they are a sequence of singly linked lists $L_{0}, L_{1}, \cdots, L_{n}$, where each $L_{i}$ contains a subset of the items in $L_{i - 1}$.

As you can see, $L_{0}$ can be considered to be the given list that will be inserted to the skip list. We also say that for an element $x$ in a skip list, we call the height of $x$ the largest value $i$ such that $x$ appears in $L_{i}$. So, for example, elements that only appear in $L_{0}$ have a height of zero.

Finally, we see that the expected length of the search path for any node u in $L_{0}$ is at most $2\log n + O(1) = O(\log n)$. I will upload another blog post with the proof, but for now, you can just assume this finding. This result shows us the power of this data structure: we can now find an element in logarithmic time, with a type of linked list that allows us easy deletion and insertion.

Some memory stuff

Before discussing the actual construction of the skip list, let's look at how we will be storing the information of the skip list.

We define a Node u to be consisting of a data value val, and an array next of pointers, where u.next[i] points to u's successor in the list $L_{i}$. For our example, if u is the first node (with the value 1), then we say u.next[0] is the second node (with the value 7), or u.next[3] is the sixth node (with the value 21).

An implementation of this node structure in C++ would be as follows.

1
template<typename T>
2
class Node {
3
public:
4
    T val;
5
    vector<Node<T> *> next;
6
    Node(T _val, int h) : val(_val) {
7
        next = vector<Node<T> *>(h + 1);
8
    }
9
};

This way of implementing the structure allows us to have low space complexity. If $n$ is the length of our skip list and $h$ is the height of our skip list, then the memory complexity would be $O(h \times n)$. What's more, we already know the value of $h$. Since the search path of finding an element is no greater than $O(\log n)$, the height can't be greater than $\log n$ too, meaning that the memory complexity of this data structure is actually $O(n\log n)$. Quite good, huh?

Spoilers...

Do you remember when I said the heights and the placement of these express lanes were quite arbitrary? In fact... they are random! We are actually able to generate $L_{i}$ from $L_{i - 1}$ by throwing coins. Specifically, for each element $x$ in $L_{i - 1}$, we throw a coin, and if it comes up tails, we add that element to $L_{i}$. This process ends when we create a list that is empty.

If you had a keen eye, you would spot that this doesn't help much in our case, since we're not creating a skip list from a known list of elements, we are adding to the skip list one-by-one — that is literally the whole point of a priority queue. But if you had an even more keen eye, you would see that the height of an element $x$ corresponds to this thought experiment:

Toss a coin repeatedly until the first time it comes up heads. How many times did it come up tails?

When we are adding an element $x$ into the skip list, we can recreate this to determine the height of $x$.

Also notice that this probabilistic behaviour doesn't need to be limited by a coin toss (which is a $\frac{1}{2}$ probability), we can change this value to change the memory and time complexity to be as desired.

Time to write some code

First, let's look at the main structure of our skip list class.

1
template<typename T>
2
class SkipListPQ {
3
public:
4
    int MAX_LEVEL;
5
    double PROB;
6
    int level;
7
    int size;
8
    Node<T> *head;
9

10
    SkipListPQ(int max_level, double prob) : MAX_LEVEL(max_level), PROB(prob) {
11
        level = size = 0;
12
        head = new Node<T>(T(), MAX_LEVEL);
13
    }
14

15
    int get_size() { return size; }
16
};

In the constructor, we set the maximum level (the height) that the skip list can have and the probability value mentioned above. We also create the head (or the sentinel) node which will be the entry point to our skip list.

To add an element $x$ into the priority queue, we must first find the location we want to add; in other words, we need to find the greatest element $y$ such that $y < x$.

Following the search path for $y$ is easy enough: when situated at some node u in $L_{i}$, we look right to u.next[i].val. If x >= u.next[i].val, then we take a step to the right in $L_{i}$, otherwise we move down into $L_{i-1}$.

1
Node<T> *u = head;
2
for (int i = level; i >= 0; i--) {
3
    while (u->next[i] != nullptr && u->next[i]->val < x) {
4
        u = u->next[i];
5
    }
6
}

In the end, u would be pointing to the element $y$ we want. Now, we can just roll for the height of the new element and change the connections inside the linked lists.

The problem is... We're not going to just connect the new element from $L_{0}$. We might roll quite unluckly and get a tall node, which we would need to connect it with the previous nodes from the start. This means that we need to store some of the nodes as we process through the skip list — going downwards. For this, we just need to keep track of the nodes at which the search path goes down from some list $L_{i}$ to $L_{i - 1}$. We can store this in an array (or a std::vector for you C++ heads) update. Precisely, update[i] is the node in $L_{i}$ where the search path proceeds down to $L_{i-1}$. Therefore, the nodes that we will modify to insert the new element are precisely the nodes update[0], update[1], ..., update[r]. Keeping track of the update vector is easy for the search path too. The change is:

1
Node<T> *u = head;
2
vector<Node<T> *> update(MAX_LEVEL + 1);
3
for (int i = level; i >= 0; i--) {
4
    while (u->next[i] != nullptr && u->next[i]->val < x) {
5
        u = u->next[i];
6
    }
7
    update[i] = u;
8
}

Now, we need to get the height of the new element: int h = random_level();. For this, we can continously get a random number and check if it is less than our PROB value.

1
int random_level() {
2
    int h = 0;
3
    double r = rand() / (double) RAND_MAX;
4
    while (h < MAX_LEVEL && r < PROB) {
5
        h++;
6
        r = rand() / (double) RAND_MAX;
7
    }
8
    return h;
9
}

Note that, since I'm using C++ here, rand() returns a random integer value, instead of a random number between 0 and 1, like most other programming languages, which is why we need to divide by RAND_MAX. That while loop can be done with a do-while loop, but I leave that to you to be more cool.

As a side note, you can also generate a random integer and check the number of leading ones to determine the height.

If the new height we get from the method is greater than the height of the skip list, we need to increase it.

1
int h = random_level();
2
if (h > level) {
3
    for (int i = level + 1; i <= h + 1; i++) {
4
        update[i] = head;
5
    }
6
    level = h;
7
}

Finally, we create our new node and connect it up with the rest of the skip list.

1
Node<T> *n = new Node<T>(x, h);
2
for (int i = 0; i <= h; i++) {
3
    n->next[i] = update[i]->next[i];
4
    update[i]->next[i] = n;
5
}

All in all, we have the following for adding an element into the skip list.

1
void push(T x) {
2
    Node<T> *u = head;
3
    vector<Node<T> *> update(MAX_LEVEL + 1);
4
    for (int i = level; i >= 0; i--) {
5
        while (u->next[i] != nullptr && u->next[i]->val < x) {
6
            u = u->next[i];
7
        }
8
        update[i] = u;
9
    }
10
    
11
    int h = random_level();
12
    if (h > level) {
13
        // We need to increase the height of the skip list
14
        for (int i = level + 1; i <= h + 1; i++) {
15
            update[i] = head;
16
        }
17
        level = h;
18
    }
19
    
20
    Node<T> *n = new Node<T>(x, h);
21
    for (int i = 0; i <= h; i++) {
22
        n->next[i] = update[i]->next[i];
23
        update[i]->next[i] = n;
24
    }
25
    
26
    size++;
27
}

Continuing on, top() is trivial. We only need to get the first element, and we use head.

1
T top() {
2
    if (size == 0) return T();
3
    return head->next[0]->val;
4
}

I'm returning the default value for our type here, but you could also just throw an exception if the size is zero.

Finally, we only got pop() to implement. Since, we're just removing the first element from the skip list, we can just change the pointers of head to the element after the element that it is currently pointing at. We also need to consider the height of our entire skip list going down, which only happens when the element we removed had no successors.

1
bool pop() {
2
    if (size == 0) return false;
3
    for (int i = level; i >= 0; i--) {
4
        // We only remove from the head
5
        if (head->next[i] != nullptr) {
6
            head->next[i] = head->next[i]->next[i];
7
            if (head->next[i] == nullptr) {
8
                // Skip list size has gone down
9
                level--;
10
            }
11
        }
12
    }
13
    size--;
14
    return true;
15
}

And... That's it! If we put everything together, we get the following.

1
template<typename T>
2
class Node {
3
public:
4
    T val;
5
    vector<Node<T> *> next;
6
    Node(T _val, int h) : val(_val) {
7
        next = vector<Node<T> *>(h + 1);
8
    }
9
};

1
template<typename T>
2
class SkipListPQ {
3
public:
4
    int MAX_LEVEL;
5
    double PROB;
6
    int level;
7
    int size;
8
    Node<T> *head;
9
      
10
    SkipListPQ(int max_level, double prob) : MAX_LEVEL(max_level), PROB(prob) {
11
        level = size = 0;
12
        head = new Node<T>(T(), MAX_LEVEL);
13
    }
14
    
15
    int get_size() { return size; } 
16
    
17
    int random_level() {
18
        int h = 0;
19
        double r = rand() / (double) RAND_MAX;
20
        while (h < MAX_LEVEL && r < PROB) {
21
            h++;
22
            r = rand() / (double) RAND_MAX;
23
        }
24
        return h;
25
    }
26
      
27
    void push(T x) {
28
        Node<T> *u = head;
29
        vector<Node<T> *> update(MAX_LEVEL + 1);
30
        for (int i = level; i >= 0; i--) {
31
            while (u->next[i] != nullptr && u->next[i]->val < x) {
32
                u = u->next[i];
33
            }
34
            update[i] = u;
35
        }
36
          
37
        int h = random_level();
38
        if (h > level) {
39
            // We need to increase the height of the skip list
40
            for (int i = level + 1; i <= h + 1; i++) {
41
                update[i] = head;
42
            }
43
            level = h;
44
        }
45
        
46
        Node<T> *n = new Node<T>(x, h);
47
        for (int i = 0; i <= h; i++) {
48
            n->next[i] = update[i]->next[i];
49
            update[i]->next[i] = n;
50
        }
51
          
52
        size++;
53
    }
54
      
55
    T top() {
56
        if (size == 0) return T();
57
        return head->next[0]->val;
58
    }
59
      
60
    bool pop() {
61
        if (size == 0) return false;
62
        for (int i = level; i >= 0; i--) {
63
            // We only remove from the head
64
            if (head->next[i] != nullptr) {
65
                head->next[i] = head->next[i]->next[i];
66
                if (head->next[i] == nullptr) {
67
                    // Skip list size has gone down
68
                    level--;
69
                }
70
            }
71
        }
72
        size--;
73
        return true;
74
    }
75
};

Further discussion

In this blog post so far, I've talked about how a skip list structure can be used to implement the interface of a priority queue; however, skip lists are much more than that. Particularly, we can use them to implement a set. Skip list implemention of a set have the same asymptotic expected time bounds as balanced trees (or red-black trees, just like how C++ std::set implements it) and are simpler, faster, and use less space. You can find that implementation on the GitHub repo for this post, in addition to the priority queue implementation of skip list in C++ and Java.

Apart from using this algorithm in a job interview, skip lists are highly useful in implementing concurrent priority queues with less lock contention (see: Skiplist-Based Concurrent Priority Queues). This is useful in decentralised contexts.

But, do you know what's the issue with skip lists? It's obviously that I can't access and modify any element I want. But, in fact, we can create an efficient random-access list/vector/array implementation with skip lists. To do it, we only need to consider the "length" of these express lanes inside the skip list.

Notice that the length of the upper layers is the sum of the lengths of the layer underneath it. This way, we can go through the skip list, counting all the lengths until we find our desired location. I've added this implementation in the GitHub repo as well.