A tree is a connected graph which contains no cycles, meaning there is only one path from one node to another if you aren't traversing the same edge twice.
Every tree can be presented as a hierarchy of nodes, with some arbitrary 'root' node. Say we took '0' as the root node, here's what the hierarchical presentation would look like:
This is called a 'rooted tree'. I've made the tree directed to express it's hierarchical nature. '0' is the root, and all adjacent nodes are its children. This means the parent of nodes '1', '2', and '3' is 0. In the same way, '1' is the parent of '4' and '4' is the child of '1'. Every node except the root node has a parent. By the way you'll end up with this kind of structure regardless of the node you choose as a root, for example if we use '2' as the root we get this:
Now that we've established that these trees are directed I'll stop using the arrows for simplicity (and because drawing arrowheads on paint is harder than it looks) as soon as my copy-pasting is done.
So let's knock out some more terminology. A 'leaf' is a node with no children i.e. all the nodes at the bottom. This makes sense considering in real trees, leaves don't have anything else growing out of them. Also similarly to real trees, we consider all non-leaf nodes to be 'interior' nodes. Similar to genealogy trees, all nodes on the path from the root (including the root) to a particular node are considered to be that node's 'ancestors'. Technically this includes the node itself but if you want it to exclude the node itself you can use the term 'proper ancestors'. In the above tree, the ancestors of '4' are '4', '1', '0', and '2'. And the 'proper' ancestors are '1', '0', and '2'. Same deal with descendants; If node u is on the path to node v from the root (including the root), then node v is a descendant of node u and if you consider the possibility that node u is node v then a node is its own descendant, hence why the term 'proper descendant' exists where a node is not its own proper descendant. In practice, most people say ancestor and mean proper ancestor, including wikipedia, but I'm sticking to the original definition because using 'ancestor'/'proper ancestor' (original definition) is better than using 'ancestor or the node itself'/'ancestor' (more common definition). Also a grandfather node is the parent of a node's parent, and a grandchild node is a child of a node's child. So '0' and '4' make a grandfather/grandchild pair, as do '2' and '3'. Siblings are nodes with the same parent.
A 'subtree' of node v is a tree which is 'rooted' at a child of v. For example in the above tree we can say that if we cut the edge between '0' and '1' then '1' and '4' would make their own tree with '1' being the root i.e. the tree is rooted at '1'. Thus we can say that the part of the tree containing '1' and '4' is a subtree of '0'. A subtree can consist of only 1 node so '5' is a subtree of '2'.
The 'size' of a tree is simply the number of nodes. The 'level' (or 'depth') of a node is the number of edges you need to traverse to get from the root to the node i.e. the length of the path from the root to the node. The height of a node length of the longest path from that node to a leaf (without going up any levels).
The 'height' of a tree is the height of that tree's root so the height of the tree above is 3. If a tree with 2 nodes has a height of 1 and a tree with one node has a height of 0 then it follows that a tree with no nodes i.e. an empty tree has a height of -1. Although this breaks the definition, it's convenient considering we usually return '-1' when something goes wrong so if you're asking for the height of a tree assuming it's got a few nodes and it returns '-1' then you think ahhh it's empty.
N-ary trees are trees which put a limit on how many children a node can have. If you want to impose a one-child policy on a tree, then you'd have a 1-ary or unary tree which would really just be a linked list. Allowing a max of two children gives you a binary tree (the subject of this post which we are yet to reach) and three children gives you a ternary tree. Then there's quaternary, quinary, senary, septenary, octonary. The tree above is a ternary tree because no node has more than 3 children.
A 'full' N-ary tree is one where for each level r, the number of nodes is N^r. So for a binary tree of height 3, a full binary tree will have 2^0 = 1 node in level 0, 2^1 = 2 nodes in level 1, 2^2 = 4 nodes in level 2 and 2^3 = 8 nodes in level 3 which totals to 1 + 2 + 4 + 8 = 15 nodes. That number is 1 less than 2^4 and if you add another level i.e. 16 nodes you'll get 31 nodes which is one less than 2^5. The pattern here is that for a full tree of height h you'll have 2^(h+1) - 1 nodes. The binary tree below has a height of 3 and thus has 2^(3+1) - 1 = 15 nodes.
A 'complete' tree is one where each level except the last one contains the max number of nodes. As for the last level, it doesn't need to contain the max number of nodes but it does need to have no gaps going from left to right i.e. if you scanned from left to right, you'll see node, node, node, node, empty slot, empty slot, empty slot etc. If you started from a tree with 1 node and added child nodes left-to-right, level by level in the same way the words I'm typing go left to right, line by line, you'll always have a complete graph.
Alright so we've nailed the terminology and we can now dive into the two types of binary trees that people will usually think of when they hear the term 'binary trees': Binary Search Trees and Heaps.
Binary Search Trees:
With these trees, each node has a value (which I'll call a 'key' from now on) and if it has a left subtree then its key is greater than the key of all the nodes within that subtree, and if it has a right subtree then its key is less than the key of all the nodes within that subtree. This is called 'symmetric' order. We're going to assume each key is unique or we would be in a bit of trouble with ordering nodes whose keys are identical.
If you can recall, last post we talked about how trees are represented as linked lists with each node being the root of a list of edges connected to that node. With binary trees it's a bit different, as we know each node can only have at most two children so it's easier to give it 4 elements: identifier (something form of identifier like 'Jake', key (a value used to compare the node to others), left (a pointer to the left child) and right (a pointer to the right child). Because we only care about the keys of each node we can ignore the 'identifier' element and just use the key itself to identify the node. Most languages will have you write mynode.left to refer to the 'left' element of the node i.e. the pointer to the left child node and the same with mynode.right, mynode.key etc. Also, a tree can be referred to via a pointer to its root.
The first operation we're going to learn is the inorder-walk where you go through the nodes and do something to all the nodes going from lowest to greatest key. We might be trying to add our keys to an ordered list. Let's use the below graph:
Here's our algorithm:
0 InorderWalk(Tree):
1 if (Tree != NULL) { // if the node actually exists
2 InorderWalk(Tree.left)
3 List.add(Tree.key) //add our node's key to the list
4 InorderWalk(Tree.right)
5 }
And that's it! Let's walk through the algorithm as it applies to the above tree. You first input the pointer to the root node '3' and as this pointer is really taking you to a node (it isn't null) you move on to line 2. Line two just tells you to repeat the process for for the root node's left subtree (which has, as its root, '3's left child '2'). So here we do the same thing, check whether the pointer is null and because it isn't we do line 2 again, meaning now we're doing the algorithm for '2's left child which is '1'. Repeat the process for '1' but it's pointer to its left child is null because it doesn't have a left child, meaning that this call of the algorithm terminates and we go back up one level and find ourselves back at node '1', and we're now at line 3 meaning we just add '1' to the list. Then we call the algorithm for its right child but once we get to line 1 of that recursion we'll work out '1' doesn't have a right child so we go back up again and now we've passed line 5 of the algorithm for the '1' node so that call terminates and we go back up to a level to the call which had node '2' as the input. At this point we're at line 3 and we can add '2' to the list, then we get to line 4 and do what we just did with node '1'; work out node '2' has no right child and so go back up the recursion chain until we're back to the root. Here we're at line 3 so we can add the root and then do the algorithm for its right subtree. This continues until we have our list [1,2,3,4,5,7,8].
Here is a poorly drawn description of the process. The blue arrows representing recursive calls (also known as 'winding') and the red arrows represent call terminations (also known as, wait for it, 'unwinding'). The unwindings that occur at the null nodes (i.e. the non-existent nodes) are due to line 1 and all the other unwindings are just the result of getting to the end of the recursive call's code. I might need to do a post on recursion later to explain this a bit better.
Anyway if anything this should show you that binary search trees are good for storing keys which are easy to put into a sorted list. If we didn't know that lower keys end up in left subtrees and greater keys end up in right subtrees we would need to sort through the whole tree and add the minimum to the list with each search.
Speaking of searching let's look at that. The idea is similar to above except that we'll never need to go back up the tree meaning we won't need to use recursion (as right now we don't have a 'parent' element for the nodes meaning we have no way to go up the tree unless we're backtracking recursive calls or we stored some stuff externally). All we need to do is look at the root and if our target key is less we look at the left child node and if our target is greater we look at the right child node and if the target key is the current node's key then we return the pointer to that node and if we reach a null pointer it means the target isn't in the tree.
0 Search(target,node):
1 while (node != NULL and target != node.key) {
2 if (node.key < target) {
3 node <-- node.left
4 } else {
5 node <-- node.right
6 }
7 }
8 return node
So here we just keep looking until either we've fallen off the tree (reached a null pointer) or our node's key matches the target key and in both cases we return the pointer to the node. This means if the algorithm returns a null pointer, the target isn't in the tree. Using the above tree as an example, if I was looking for '6', I'd start at the root, realise 6 > 3, look at 7 and realise 6 < 7, look at 5 and realise 6 > 5 and then look at 5's right child and realise it doesn't exist i.e. the pointer is null so I return null. The reason I used 'node' instead of 'tree' in this one, despite them both referring to nodes/ the roots of trees, is that here you're not fully traversing each subtree and you only really care about the nodes and their children. It's really just something to help me conceptualise it.
Next operation we'll learn is finding the minimum key of a tree. Fairly simple, we just keep going to the next left child until we find a node with no left child, and then return this node:
0 Minimum(node):
1 while (node.left != NULL) {
2 node <-- node.left
3 }
4 return node
With the above tree if we would input the pointer to the root, '3', and then it would change the pointer to '3's left child '2' and then it would change the pointer to '2's left child '1' and then considering '1' has no left child i.e. node.left = null, it returns the pointer to '1'. If we only cared about the subtree rooted at '7' we would input a pointer to '7' and the algorithm would return '4's pointer.
Finding the minimum of a subtree is useful in finding the successor of a key. In the above tree with the keys 1,2,3,4,5,7,8 the successor of 5 is 7 i.e. the next largest key. If you want to know the successor of a particular node's key, and it has a right subtree, all you need to do is find the minimum of that tree because everything in the right subtree is larger than the current node's key and you want the minimum of those keys. But what if your node has no right children? This means that in order to find the successor you need to travel up the tree until you have to go to the right to get to the parent i.e. the current node is a left child, meaning its parent is greater and you don't need to keep looking because anything further to the right will be even greater than that. Let's say we have a node '6' in the above tree and it's the right child of '5'. Finding its successor involves going up the tree until you can go right and so we find that '7' is '6's successor.
If we want to implement this algorithm then we'll need to store a pointer in each node which takes us to that node's parent which we'll call node.parent. If node.parent is null then the node is the root of the tree. Also if in our algorithm we find out that node.parent is null then we should return null because it means there is no successor to the node we inputted e.g. if we inputted a pointer to '8' then we'd simply go up the tree until we reach the root and then return its parent i.e. null. We'll store the pointer to the current node's parent as 'above'.
0 Successor(node)
1 if (node.right != NULL) {
2 return Minimum(node.right)
3 } else {
4 above <-- node.parent
5 }
6 while (above != NULL and node == above.right) {
7 node <-- above
8 above <-- above.parent
9 }
10 return above
To find a node's predecessor all we have to do is exchange Minimum with Maximum and right will left. The algorithm which finds the Maximum is the same as the Minimum one except it exchanges left for right.
Inserting a node is similar to the search algorithm but when you find a null pointer you want to plug the node in there. We'll assume the new node is already in RAM somewhere and we will input a pointer to the node called 'new'. We'll also input the root of the tree as 'node'.
0 Insert(new, node):
1 if (node == NULL) {
2 node <-- new
3 return
4 }
5 while (TRUE) {
6 if (new.key > node.key) {
7 if (node.right == NULL) {
8 node.right <-- new
9 new.parent <-- node
10 return
11 }
12 node <-- node.right
13 } else {
14 if (node.left == NULL) {
15 node.left <-- new
16 new.parent <-- node
17 return
18 }
19 node <-- node.left
20 }
21 }
This isn't the only way to do the code: you could have done it like this:
0 Insert(new, node):
1 if (node == NULL) {
2 node <-- new
3 return
4 }
5 while (node != NULL) {
6 above <-- node
7 if (new.key > node.key) {
8 node <-- node.right
9 direction <-- right
10 } else {
11 node <-- node.left
12 direction <-- left
13 }
14 above.direction <-- new
15 new.parent <-- above
This code assumes you're programming language will let you make a variable (direction) that refers to an element of a node.
Here's a recursive approach from a youtube channel called mycodeschool:
1 if(root == NULL) root <-- new
2 else if(key < root.key) root.left = Insert(root.left,key)
3 else root.right = Insert(root.right,key)
4 return root
To understand how this last one works, just read on to deletion where an almost identical block of code gets some analysis.
Now onto our last operation for binary search trees: deletion. This is by far the most complex but some sneaky recursion will get us through it. We'll use the tree below (also we'll ignore the .parent element for this):
Let's say we wanted to delete node '1'. This is easy, just deallocate the memory in RAM for '1' and set '3's left child pointer to null. So much for nodes with no children.
What about nodes with one child? Let's look at trying to delete '7'. We can just deallocate the memory in RAM for '7' and then set '5's right child to '9':
So the brown part there is us deallocating the memory for '7' which includes its pointer to '9'. The red part is us cutting the tie between '5' and '7' by replacing '5's right child pointer with one that leads to '9' instead of '7' (the blue arrow). Let's look at how our tree looks now:
An important question to ask is; is this still a binary tree? We know that 9,8 and 11 are greater than 5 because they were the child of a node which was greater than 5 as '7' was '5's right child. This means our deletion was completely harmless to the structure because we've retained the property that the nodes in the right subtree of a node have greater keys. If we wanted to delete a node whose one child was a left child, the structure would also be retained. So we've done nodes with no children, nodes with one child, all that's left are nodes with two children. The problem here is deciding which node will take its place. Looking at '9', if we wanted to remove this we could replace its key with 8 or 11 and then delete the node whose key took '9's place, and the structure would stay i.e. if '8' became the new '9', 11 > 8 so the structure is kept and if '11' became the new '9', 8 < 11 so the structure is kept.
Considering the symmetry, let's just say we're going to grab replacements from the right subtree each time we want to delete an interior node (in this case that means using the top alternative).
What if we wanted to delete '15' from the above tree? To make a point, I'll throw a '16' into the tree as '17's left child:
In this situation we can't just take '17' and put that in '15's place because then '17's right subtree will contain 16, 18 and 20 and the 16 being there is not good considering all the values should be greater than 17. The better alternative would be to get the minimum of '15's right subtree and use that as a replacement. The first benefit of this is that we know all other values in the subtree are going to be larger meaning when '16' takes '15's place the structure will hold because the remaining right subtree will still have values greater than 16. The second reason is that minimum values often end up being leaves which themselves are easy to delete. Good thing we've already made a Minimum algorithm. So the process here would be to find the minimum key in '15's right subtree, replace '15's key with that and then delete the now-redundant minimum node from the subtree.
So that's all the possibilities: with 0 children the node simply gets deallocated, with 1 child the node gets deallocated and the gap is bridged between its parent and child, and with 2 children the minimum child in the right subtree takes the place of the node and itself gets deleted, which may involve one of the first two possibilities (but not the third because the minimum node will never have a left child so it will only ever have a max of one child).
So here is our code, you input the root of the tree and the key you want deleted. The algorithm has a recursive approach to searching for the key in the first place which helps it go back up a level to change one of the parent node's child pointers when the target node gets deleted/replaced.
1 if(root == NULL) return root // the key isn't in the tree
2 // this is the searching part
3 else if (key < root.key) root.left <-- Delete(root.left,key)
4 else if (key > root.key) root.right <-- Delete(root.right,key)
5 // here's the actual deletion part
6 else {
7 // 0 children
8 if(root.left == NULL and root.right == NULL) {
9 deallocate root;
10 root = NULL;
11 }
12 // 1 child
13 else if(root.left == NULL) {
14 temp <-- root
15 root <-- root.right
16 deallocate temp
17 }
18 else if(root.right == NULL) {
19 temp <-- root
20 root <-- root.left
21 deallocate temp
22 }
23 // 2 children
24 else {
25 temp <-- Minimum(root.right)
26 root.key <-- temp.key
27 root.right <-- Delete(root.right,temp.key)
28 }
29 }
30 return root
Let's go through this code via trying to delete the root itself, '12'. So we input a pointer to the root and the key 12. We can skip lines 1-5 because the root itself has the key we're looking for, meaning we then come to line 24 where we've worked out root.right != null and root.left != null because '12' has two children. We set a temporary pointer value to the minimum of '12's right subtree, which is '13'. We then set 13's key as '12's new key so that was the substitution step, and all that's left is to delete '13' and give the root a new pointer to its right child in case it gets changed, so we kill two birds with one stone in line 27 and just consider the right subtree by inputting '15' as the root and 13 as the key.
So we're back to line 1 in our new recursion, and at line 3 we work out 13 < 15 so we set 15's left child to whatever the result of the next recursion is, inputting '13' as the root and 13 as the key:
So now we're at line 1 again and as our root has the key we want i.e. we want to delete it, we get to line 13 where the root's left child is null and it only has a right child ('14'). So we set our temp pointer to the pointer to our root '13', then set root to '14' and then deallocate '13' which is pointed to by temp. At line 30 we then return the pointer to '14'. So now that we're back to the previous recursion we can tell '15' that its new left child is '14' because the pointer to '14' was returned and assigned to root.left in line 3.
and the cleaner-looking result:
So now that that's done we don't need to worry about any more if conditions and we end up returning our root, which is just the pointer to '15', to the previous recursion (the one we started with). We find ourselves at line 4 and we've just assigned '15' as the right child of our new '13' which it already was so no harm done there. And then we return the original root that we inputted in the first place but that's not really important because we're at the surface now and we don't need to return any more roots. Anyway the final tree looks like this:
That wasn't too hard. Notice that no matter how complex the tree is, only one deallocation of memory will take place and before that there'll just be a number of key substitutions.
Alright that's all there really is to the structure and operations of binary search trees!
Moving on, let's focus on heaps.
Where the one thing determining the structure of binary search trees was the condition that for a certain node's key, the keys of the left subtree must be smaller and the keys of the right subtree must be larger, with heaps we have something slightly simpler. For a max-heap, a parent node's key must be greater than the keys of its children (and for a min-heap, swap greater with lesser). Unlike in binary search trees we can say 'children' rather than 'subtrees' because if the heap-property (what this condition is called) is satisfied for each node then logically, a node's key will be greater than the keys of its two subtrees, whereas with binary search trees it was possible for a each node to have a key greater than its left child and lesser than its right child but for the structure not to be valid (imagine the root is '3', its two children are '1' and '9' and '9' has a left child of '2'; this isn't a valid structure). So how convenient for us now that we're dealing with heaps!
The second thing about heaps is that they are complete trees i.e. the only level of nodes that may not be filled will be the bottom one and all the nodes on the bottom level are on the left hand side. This is called the shape property. The shape property is what gives us an incentive to use an array to store the values rather than the linked data structure. Consider a binary tree which is built from a list of elements [10, 9, 4, 14, 16,18]. This would not end up being complete. What if they were inputted like [14,10,4,9,16,18]. Still not complete. What about [4,9,10,14,16]. This is just atrocious because it's basically a linked list.
So for some binary trees it is simply impossible to be represented as a complete tree, and even more so, the order in which keys are fed into the tree can leave you with degenerate graphs i.e. the last one there. This often leads to a fair bit of wastage with null pointers but it's nothing compared to the wastage that would occur if you tried representing the tree with an array as you would need an element for every possible node. For that degenerate tree, it's got 6 levels so a full tree with that many levels has 2^6 - 1 = 63 nodes meaning you'd be wasting 63 - 6 = 57 element slots in the array. On the other hand, no matter what elements you put into a heap, it can be represented by a complete tree (in fact it's a necessity given the shape property). This means arrays are far better suited towards heaps which can have a node for each element in an array.
So lets look at how you could represent a heap in an array. It's kind-of similar to the arrays storing triangular matrices.
Our array is called A and each node has an element in A. The children of A[i] are A[2i +1] and A[2i + 2] and the parent of A[i] is A[floor((i-1)/2)]. If we had an array with indexes starting at 1 this would be slightly cleaner but base 0 arrays are the life-force of computer science so we'll go with that. Anyway it is absolutely awesome that you can so efficiently store heaps, although I guess that's in part why they were invented in the first place.
Let's look at some operations. We'll only consider min-heaps because the difference between min and max heaps is trivial. First up is insert which is going to require a dynamic (resizable) array. You append the new key to the end of the array and then compare it to its parent and if it is larger then you've got no problem but if it's smaller you need to swap the two. Say we want to insert '2' into the heap above. It starts at the bottom-right and because 2 < 6 it gets swapped with '6'. A this point the heap-property from '2' down is conserved because 8 > 6 and 6 > 2 so 8 > 2 meaning we don't need ever to worry about how the left child gets affected. But we're not done because now we need to compare '2' to its parent again and this time 1 < 2 so the heap is fine and the insertion is done. Here's some pseudocode for insertion where you input the array A and the new key.
0 Insert(A,key):
1 add key to A
2 i <-- length(A) - 1
3 while (A[floor((i-1)/2)] > A[i]) {
4 swap(A,floor((i-1)/2),i)
5 i <-- floor((i-1)/2)
6 }
Toooo easy. Let's try deletion. With heaps you can only delete the root from the tree (similar to how you can only delete the element at the front of a queue) but this means you need to replace it with something. You could replace it with the next best thing but then that needs to be replaced by something and it's strenuous to follow that chain down to the last element in the array (and you would need to do this because otherwise you won't have a complete tree by the end) let alone have a heap left over by the time you've done all the swaps. A better way is to just swap the last element in the array with the root, then delete the root. Now you've got a root which is not going to satisfy the heap property because it will be larger than its children so we can just swap it with the smaller one (meaning the new root will be smaller than both its children) and repeat the process until the key which started at the bottom has trickled back down there, leaving behind a heap which satisfies both the heap and shape properties. By swapping the root with the last element we ensure the shape property is preserved because once you've deleted the key you wanted to delete, the tree is still complete and after that all you're doing is swapping meaning it will stay complete.
The deletion part (we'll call it Extract-Min) involves swapping the root with the last element and deleting it. The rearranging part is called min-heapify-ing. The min heapify function takes a parent (A) and its two children (B and C) and satisfies the heap property for them, and if A needed to be swapped for that to happen then it repeats the process for A and its new children until A is smaller than its children. This assumes B and C are already smaller than their children when the process starts so we only need to worry about A, and luckily this is the exact situation we have when we swap the root of a heap with the last element and try and satisfy the heap property again through a number of swaps.
0 ExtractMin(A):
1 min <-- A[0]
2 swap(A,0,length(A) - 1)
3 remove A[length(A) - 1]
4 Min-Heapify(A,0)
5 // the return is for if you wanted to 'pop' the root off the heap
6 return min
1 left <-- 2i + 1
2 right <-- 2i + 2
3 smallest <-- i
4 if (left <= length(A) - 1 and A[left] < A[smallest]) {
5 smallest <-- left
6 }
7 if (right <= length(A) - 1 and A[right] < A[smallest]) {
8 smallest <-- right
7 if (right <= length(A) - 1 and A[right] < A[smallest]) {
8 smallest <-- right
9 }
10 if (smallest != i) {
11 swap(A,i,smallest)
12 Min-Heapify(A, smallest)
10 if (smallest != i) {
11 swap(A,i,smallest)
12 Min-Heapify(A, smallest)
13 }
In terms of complexity we first build the heap which is O(n) and then we get each node (O(n)) and potentially move them all the way to the leaves (this is the worst case for half the nodes at least) which is O(logn) meaning we end up with O(n) + O(nlogn) which is O(nlogn), so it's a pretty good complexity for a sorting algorithm.
The final operation we're going to look at for heaps is building a heap i.e. taking an array of keys and rearranging it so that the heap property is satisfied. There are two ways of doing this: the sift-down approach and the sift-up approach. When we dealt with insertions you would put your new key at the bottom of the heap and then it would be compared to its parent and if smaller it would be swapped with the parent. This process is called sifting-up. With deletions you're getting the last element and then making it the root and allowing it to go back towards the bottom until it finds a place where it's no longer violating the heap property. This is called sifting down, which uses the min-heapify function.
The sift-up approach it to just get your array and start inserting elements into your heap from scratch. So you may have 15 elements but at the beginning you only look at the first and you make that the root, then you look at the 2nd and that goes one level down and swaps with the root if need be, then this process continues with adding more to the heap and having them sift up towards the top if they need to. Every single element will need to be inserted so we know our complexity is at least O(n), but we also need to consider how many moves each element may take once it's in the heap. When you insert the root (level 0) it can't move because it's the only node in the heap. Then in the next level (level 1) you'll have two nodes which each may need to move to the top level i.e. one move. Then on level 2 you've got 4 nodes which each may move 3 times. The pattern here is that for any level k you'll have 2^k nodes moving k times in the worst-case. So the total amount of moves is going to be:
2^0 * 0 + 2^1 * 1 + 2^2 * 2 + 2^3 * 3 ... + 2^h * h where h is the height of the completed heap.
We worked out above (far far above) that the #nodes in a binary tree is given by 2^(h+1) -1. Working backwards, the height h is log2(n+1)-1. However for different #nodes you will get the same height e.g. 4,5,6 and 7 nodes correspond to a height of 2. The solution is to ceil the log2(n+1) part so that an incomplete row will be considered a full row because either way it causes the same height, hence h = ceil(log2(n+1))-1. That whole ceiling thing is just a technicality which doesn't matter for this next part. So if we substitute that equation into the 2^h * h above we get 2^(ceil(log2(n+1))-1) * ceil(log2(n+1))-1 which is O(nlogn) because the first bit is O(n) and the second bit is O(logn), and all the hairy parts just fall out as constants or smaller terms. So knowing that complexity, the complexity of 2^0 * 0 + 2^1 * 1 + 2^2 * 2 + 2^3 * 3 ... + 2^h * h is also O(nlogn) because all the smaller terms don't matter compared to 2^h * h and the processing cost per move will just be an arbitrary constant. Not too bad as far as complexity goes.
Here's the pseudocode: (you'll need two lists, the list that you get your keys from (B) and the list for the heap itself (A))
0 Build-Heap-One(A,B):
1 for i <-- 0 to length(B) - 1
2 insert(A,B[i])
The sift-down approach works from the bottom-up. You look at all the bottom interior nodes (you can ignore the leaves because they don't have any children and thus already satisfy the heap property) and compare them to their children and if swapping needs to happen, do so. Then go one level up and do the same, looking at the roots and swapping them down if you need to; potentially down to the leaf level. The beauty of this approach is that you get to ignore all the leaves which make up half the elements. So there will be 2^h leaves and you don't need to move any (they may be moved on behalf of higher nodes later but that will be factored in to the total number of moves), and there will be 2^(h-1) nodes above that level and they will do a max of 1 move, and the nodes above them will do a max of two moves, all the way to the root which will do a max of h moves. So the total number of moves is:
2^h * 0 + 2^(h-1) * 1 + 2^(h-2) * 2 ... + 2^0 * h
This is exactly the same as what we had below except that the 2^x terms have been reversed. Here's what our two #moves sums look like:
We already worked out the top-down insertion approach was O(nlogn) so let's see what we can get out of our bottom-up approach:
So if our sum is O(logn) then we'll end up with that same complexity as the top-down approach, but if we can show that it's O(1) (i.e. it's just a constant) then it means our total complexity is O(n) * O(1) = O(n). Let's take the absolute worst case scenario and say that the height of our heap if infinity i.e. h = infinity and if the sum proves to be a constant then obviously for any h our sum will be a constant. Well I'm not going to prove it here but the infinite series k/2^k converges to 2 i.e. it is bounded by a constant meaning the sum for any h is O(1) and so our total complexity for the bottom-up approach is O(n). An intuitive explanation for why it has a lower complexity is that with the sift-up approach we had majority of nodes (the leaves) having to move the most for the worst case scenario and the root having to move the least, whereas here we have the leaves not moving at all and the root is the node which moves the most in the worst-case. So we have a whole lot less moving; so much so that for enormous values of n we never have more than 2n moves when building the heap.
Here's the pseudo-code: (We don't need two lists to do this because it works in-place)
0 Build-Heap(A):
1 for i <-- floor((length(A) - 1)/2) downto 0
2 Min-Heapify(A,i)
Now that we know how to build a heap and how to extract the root of the heap we can combine some functions to make a heap-sort. The idea is to build a heap from an array of unsorted items and then keep extracting the root (which will always be the minimum) and putting that into another list. A is the unsorted list which we use to store the heap and B is the sorted list:
0 Heapsort-One(A,B):
1 Build-Heap-Two(A)
2 for i <-- 1 to length(A)
3 add ExtractMin(A) to B
This is pretty good but it would be better to do an in-place sort. If we use a max-heap where the root has the greatest key, we can continually extract it from the top of the heap and put it at the end of the array rather than putting it in a new array. The extract function we have already swaps the root with the last element and then removes it but we want to change that a bit: We want to not delete the root after we move it to the end of the array and instead just move a pointer that points to the left of it which indicates the new 'last' node in the heap. That way we can continually remove the max from the heap, put it into our sorted list which grows from right-to-left, and end up with an empty heap and a sorted list. Here's the code, with modified functions to help us out: (the extract-max has just been melded into my heapsort algorithm in the for loop)
0 Heapsort(A):
1 Build-Heap(A)
2 for end <-- length(A) - 1 downto 1
3 swap(A, 0, end)
4 Max-Heapify(A, 0, end - 1)
0 Max-Heapify (A, i, end):
1 left <-- 2i + 1
2 right <-- 2i + 2
3 largest <-- i
4 if (left <= end and A[left] > A[largest]) {
5 largest <-- left
1 left <-- 2i + 1
2 right <-- 2i + 2
3 largest <-- i
4 if (left <= end and A[left] > A[largest]) {
5 largest <-- left
6 }
7 if (right <= end and A[right] > A[largest]) {
8 largest <-- right
7 if (right <= end and A[right] > A[largest]) {
8 largest <-- right
9 }
10 if (largest != i) {
11 swap(A, i, largest)
12 Max-Heapify(A, largest, end)
10 if (largest != i) {
11 swap(A, i, largest)
12 Max-Heapify(A, largest, end)
13 }
In terms of complexity we first build the heap which is O(n) and then we get each node (O(n)) and potentially move them all the way to the leaves (this is the worst case for half the nodes at least) which is O(logn) meaning we end up with O(n) + O(nlogn) which is O(nlogn), so it's a pretty good complexity for a sorting algorithm.
There we go, we have now done binary search trees and heaps, next up is spanning tree algorithms.
