Binomial heap

A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in \(Θ(\log n)\) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique 'binomial trees' which are constructed from smaller binomial trees.

Just like a regular binary heap, the binomial heap can be either a min heap or a max heap. It also follows the properties of the heap data structure; all nodes must be smaller than their children for a min heap, or larger for a max heap.

The animations in this article will only work in certain browsers, it has been tested in the latest Chrome and Firefox.

Selection sort

Selection sort is an \(O(n^2)\) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

Selection sort is similar in complexity to insertion sort but almost always performs worse. This is due to the fact that selection sort has an exact number of comparisons based on \(n\), which can be defined using the arithmetic progression:

$$(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2$$

This makes its best case always contain the same amount of comparisons as its worst.

While selection sort is faster than most \(O(\log n)\) sorts for small lists, insertion sort is normally the preferable choice. It's main favourable property is that it will perform at most \(n - 1\) element swaps, so it may be useful if swapping is expensive.

Algorithm: All permutations of a set

Problem

Implement a function that gets all possible permutations (or orderings) of the characters in a string. For example for the input string "abc", the output will be "abc", "acb", "bac", "bca", "cab" and "cba".

Analysis

This problem is very similar to all combinations of a set, though the actual computing of the values will be quite different. Let's start by defining the inputs and outputs.

ArrayList<String> getPermutations(String characters);

Now let's look at how this problem is naturally solved. When I write down a set of permutations by hand, I tend to start with the first letter (a), and then find all permutations without that letter in it. So for "abc" I would write:

a bc
a cb
b ac
b ca
c ab
c ba

Algorithm: All combinations of a set

Problem

Implement a function that gets all possible combinations (or subsets) of the characters in a string with length of at least one. For example for the input string "abc", the output will be "a", "b", "c", "ab", "ac", "bc" and "abc".

Analysis

Firstly we will define our method signature. It's fairly simple as it's described in the problem, the input is a String and the output is a list of Strings

ArrayList<String> getCombinations(String characters);

Splay tree

The splay tree is type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

The worst case height of a splay tree is \(n\), this could be the case if all nodes were accessed in ascending order for example.

This makes the worst case complexity of the splay tree's operations \(O(n)\). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a \(O(\log n)\) amortized worst case time complexity for all operations.

The splay tree is a particularly good choice as a data structure when it's likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.

Binary heap

A binary heap is binary tree structure that typically uses an array as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to the fast extraction of either a minimum or a maximum element.

Heaps come in two flavours, the min-heap which allows quick \(O(\log n)\) extraction of the minimum element, and the max-heap which allows the same for the maximum value. Before it is possible to extract values, the heap must first be constructed. This is done by going through the first half of the elements (in the array) starting from the middle and calling 'heapify' on each element, running in \(O(n)\) time.

It is typical to implement priority queues using heaps due to their \(O(\log n)\) extract min/max time.

Data structure: Red-black tree

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately \(\log n\) nodes high, allowing search in \(O(\log n)\) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee \(O(\log n)\) search.

Insert and delete are also performed in \(O(\log n)\) time. The 'fixup' operations where the balancing occurs after insert and delete have quite complex implementations as you will see below. This is because we need the properties of the red-black tree to hold otherwise it may not be balanced.

Quicksort

Quicksort is an \(O(n^2)\) sorting algorithm that runs in \(O(n \log n)\) time on average. It has a number of favourable qualities; it's an in-place sort, requiring \(O(\log n)\) auxiliary space in the worst case; and is also a divide and conquer algorithm making it easy to parallelise. Unfortunately however it's not a stable sort.

It works by first selecting a 'pivot' element, then re-ordering either side of the list so that everything before the pivot is less than the pivot and everything after is greater. Quicksort is then called recursively on either side of the pivot.

Despite quicksort having a worst-case performance of \(O(n^2)\), it is sometimes regarded at the same level performance-wise as \(O(n \log n)\) sorts like merge sort or heapsort. This is due to its average case being \(O(n \log n)\), it will often perform even better in practice than the \(O(n \log n)\) sorts.

Heapsort

Heapsort is an \(O(n \log n)\) sorting algorithm that works by first constructing a heap out of the list and repeatedly pulling the root off the top of the heap and reconstructs it until there are no items left in the heap. The values that are pulled off of the top of the heap come out in sorted order. If the heap used was a min-heap, the resulting list will be in ascending order, and a max-heap will give them in descending order.

Unfortunately heapsort is not stable so sorting a list that is already sorted could quite possibly end up in a different order.

Algorithm: Binary search

Binary search is a decrease and conquer search algorithm than can be used on a sorted array. It operates by determining whether the search value is less than or greater than the middle value and recursively calling itself on the lower or upper half of the list respectively until either the value is found or not found.

The binary search algorithm is very similar to the binary search tree's search operation though not identical. Binary search's average and worst case time complexity is O(log n), while binary search tree does have an average case of O(log n), it has a worst case of O(n). Namely when the tree's height equals the number of items in the tree (incredibly unlikely in any real scenario).

The real power in binary search shows itself when we use it to search a huge list of items, much like any logarithmic algorithm. Exponential functions work by looking at the whole input data when considering each item. Logarithms (inverse-exponential functions) work by repeatedly halving the input data. Consider a list that contains 1 million items, if this list happens to be sorted we can use binary search to search for an item in no more than 20 steps.

Insertion sort

Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.

As you probably guessed, insertion sort isn't one of the fastest sorts, running in \(O(n^2)\) worst case time. It does have a few benefits however:

• It is faster than most \(O(n \log n)\) sorting algorithms for small lists.
• It is very memory efficient requiring only \(O(1)\) auxiliary space for the single item that is being moved.
• It is a stable sort; equal elements appear in the same order in the sorted list.
• It is an adaptive sort; it's fast when sorting mostly sorted lists or when adding items to an already sorted list.
• It is really easy to implement.

Merge sort

Merge sort is a sorting algorithm that runs in \(O(n \log n)\) time. It is a divide and conquer algorithm, so it can get the most out of today's multi-cored systems. It works by continually splitting up the array until each item stands on its own. The items are then merged back with the items that they were split with in the correct order.

Merge sort is also a stable sort, this means that if there are elements considered equal, they will be in the same order in the final list. This is illustrated in the below image, teal and blue (9) are in the same order in both the source and sorted lists.

Big-O Notation

Introduction

Big-O notation (pronounced 'Big Oh') is used in computer science as a means to describe the worst-case performance of an algorithm. It's one of the things you really should learn if you're interested at all in designing efficient algorithms.

The formal definition is as follows:

f(n) = O(g(n)) means c*g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c*g(n), for large enough n (i.e. , n ≥ n₀ for some constant n₀).

The Algorithm Design Manual, Steven S. Skiena

This definition is a very format way of saying that Big O-notation is the upper-bound/worst-case of a function.

Binary search tree

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete. Operations on a BST always start at the root node and work their way down, because of this they take time based on how high the tree is. For example a tree with n nodes where there are no right children will take \(O(n)\) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of \(O(\log n)\).

The A* pathfinding algorithm

Game development introduced me to programming when I was around 10, and I've loved it ever since. One of the first formal algorithms I learned before entering university was A* (pronounced A-star), and I really had a great time doing so. It is one of the most widely used pathfinding algorithms and it's likely the one you'd be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also referred to as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.