Heap Sort
Holidays and a new job have been occupying my attention for the past couple of weeks but, fear not, I’m still pursuing my algorithms project. Next up on the agenda is Heap Sort.
Heap sort, as its name implies, implements sorting via a data structure known as a heap. The specific heap structure that we’ll look at is a (binary) tree where each node in the tree has 0, 1 or 2 child nodes. Each node in the tree is assigned a value (for simplicity’s sake, we’ll assume the values are numbers but they could be any type of element which can be compared/ordered). The heaps we’ll consider are further constrained such that each node in the tree satisfies the “max heap property”; each node is greater than its children and any descendants. This type of heap is known as a Max Heap.
Let’s first consider the maintenance operation. Given a node, N, in a binary tree that has left and right sub-trees that satisfy the max-heap property, we wish to implement the “max-heapify” function which arranges node values so that the tree rooted at N satisfies the max heap property.
Implementing max-heapify is straightforward; max-heapify looks at the left and right children of node N and determines the largest among them. If node N is the largest node, we’re done – N is larger than it’s immediate children and the children are roots of max heaps so the tree rooted at N is a max heap. However, if node N is not the largest node, the routine swaps the largest node value and the value at node N; we are now guaranteed that N and its immediate children form a max-heap. The unchanged sub-tree, obviously, remains a max-heap. However, the tree rooted at the swapped (child) node may now be an invalid max-heap. To address this case, we apply the max-heapify function at the changed node – fixing that node but perhaps invalidating one of its children. We repeat this process as long as one of the children violates the max-heap property or until we reach the leaves of the tree. In this manner, the value from node N “floats down” to find its appropriate place in the heap.
Now let’s look at some sample lisp code to implement the max-heapify function.
Heap Data Structure
There are a number of possible ways to implement the heap data structure. From an OO standpoint I’m immediately inclined to implement a tree as a collection of node objects, each containing a value and pointers to two child nodes. The text implements the heap in a more efficient fashion. The values of the heap are stored in an array. The root node is placed at index 0 the left child at index 1, the right child at index 2 and so-on laying subsequent levels of the tree out from left to right in the array one after the other.
Given this implementation, for any given node N at index n, its left child is at index 2n + 1 and its right child is at index 2n + 2. By the same measure, a child’s parent is found at index ceiling(n/2 – 1). The following lisp functions implement the parent and child indexing functions.
(defun parent-idx (node-idx) (- (ceiling (/ node-idx 2)) 1)) (defun left-child-idx (node-idx) (+ (* 2 node-idx) 1) (defun right-child-idx (node-idx) (+ (* 2 node-idx) 2)
Max-Heapify and Make-Maxheap
Given the data structure above, the following lisp code will implement the heap management algorithm described earlier.
(defun max-heapify (node-idx heap)
(let ((the-max-idx node-idx))
(setf the-max-idx (max-idx the-max-idx (left-child-idx node-idx) heap))
(setf the-max-idx (max-idx the-max-idx (right-child-idx node-idx) heap))
(when (/= the-max-idx node-idx)
(rotatef (svref heap node-idx) (svref heap the-max-idx))
(max-heapify the-max-idx heap))))
This function takes an array and a node index and, as described previously, determines the max among the root node and its two children. If the routine finds that the root node was not the node with the maximum value, it swaps the values of the root and maximum value node and then recurses, applying the max-heapify function to the changed node.
The routine depends on the utility function max-idx. This function simply returns the index of the node with the largest value. In addition, I’ve implemented the routine such that it always returns the first index in the case where the second index is invalid – in other words, when the recursion reaches the leaf nodes, the max-idx function will “do the right thing”.
(defun idx-invalidp (node-idx heap) (or (< node-idx 0) (>= node-idx (length heap)))) (defun max-idx (idx1 idx2 heap) (cond ((idx-invalidp idx2 heap) idx1) ((idx-invalidp idx1 heap) idx2) ((> (svref heap idx1) (svref heap idx2)) idx1) (t idx2)))
Now let’s consider how to build a max-heap from a collection of values. We first arrange the values at random in the binary tree (array). Next we process the parents of each of the leaf nodes. Note that the leaf nodes are trivial max-heaps and so, if we process the parents of the leaves with the max-heapify function, we are guaranteed to create max-heaps rooted at those parents. If we now proceed up to the next layer of the tree (the parents of the leaf parents…) we know that each of their left and right sub-trees are max-heaps. Applying max-heapify to each of these parents then, will create max heaps. We continue in this fashion up the tree until we reach the root node. At that point, the whole tree satisfies the max-heap property.
Using an array as our data structure, a simple implementation would walk from the end of the array to the beginning and call max-heapify on each element’s parent.
(defun make-maxheap (a)
(loop for node-idx downfrom (- (length a) 1) to 1
do (max-heapify (parent-idx node-idx) a))
This works but, note that we will visit each parent node twice, we can fix this by decrementing by 2 on each iteration.
(defun make-maxheap (a)
(loop for node-idx downfrom (- (length a) 1) to 1 by 2
do (max-heapify (parent-idx node-idx) a))
Sorting
Once we’re here (creating and maintaining max-heaps) sorting is really only a short hop away. The approach is simple; first we turn our input array into a max heap using make-maxheap. Once we’ve done this, we know that the 0th element is the largest element so, we copy this value to a new sorted array. Next we remove (shorten the array by 1) the last element and replace the 0th element with that value. We now call max-heapify on the (shortened) heap. This will cause the 0th node to float down to an appropriate place in the heap (such that the max heap property is restored for the whole heap). We repeat this process until there are no more elements in the heap remaining.
The following code implements the algorithm:
(defun heap-sort (a)
(make-maxheap a)
(loop for last downfrom (- (length a) 1) to 0
collecting (svref a 0)
do
(shiftf (svref a 0) (svref a last) most-negative-fixnum)
(max-heapify 0 a)))
Note that we have been (silently) assuming the use of simple-vectors as the sequence type. Working with these is very fast but does not accommodate a fill pointer which would allow us to pop items off the end of the vector when implementing the heap-sort function. I cheat in the implementation shown above by marking the “new” end of the array with most-negative-fixnum; when the recursion encounters this value, it will terminate in the same way as if we had hit the end of the array. If we allowed ourselves the use of a vector with a fill pointer, we could have implemented the following:
(defun heap-sort-1 (a)
(make-maxheap a)
(loop for last downfrom (- (length a) 1) to 0
with b = (make-array (length a) :initial-contents a :fill-pointer t)
collecting (aref b 0)
do
(setf (aref b 0) (vector-pop b))
(max-heapify 0 b)))
If we did this, we would need to modify the other functions to use aref instead of svref ( with the possible/theoretical/who-knows? loss of some performance).
Running Time Analysis
Now we’ll take a quick look at the performance of the heap sort algorithm.
Max-heapify
Let’s first start by looking at the performance of max-heapify. In the worst case, the root node ends up as a leaf node of the heap after the routine executes. At each level in the heap, we do a constant time operation – we do (at most) two compares and a swap. So the worst-case execution time is O(height-of-the-heap) and, since we know that the height of the heap is lg(n), the algorithm is O(lg n).
Make-maxheap
Next, we look at make-maxheap. The running time is going to be the sum of the running times of the max-heapify algorithm for each node in the tree which gives us a bound of O(n lg n). This is not a tight upper bound however, as the running time of the max-heapify function is dependent on the height at which it was called; specifically, we said that the worst case for max-heapify was O(h) where h is the height of the tree. So, a tighter bound would sum the running times (h) for max-heapify calculated considering the level in the tree.
∑h=0..lg(n) (num-nodes-at-level-h) O(h)
Where h is the level in the heap measured with h=0 being the bottom, leaf nodes. We know that if we count from the top node down (if for the time being we let the top node be level 0), that we have 2^l nodes at level l (one top node, 2^0, 2 level one nodes, 2^1, 4 level 2 nodes, 2^2, etc.) So if we let H be the total height of the heap, then the number of nodes at any level h (as measured, now, with h=0 being the bottom, leaf, nodes) is 2^(H - (h + 1)) which is (2^H)/(2^(h+1)). Finally, we know that the height of the heap H, is lg(n), so the total number of nodes at any level h is n/ 2^(h+1) which we use to replace number-of-nodes-alt-level-h in the equation above.
∑h=0..lg(n) n/2^(h+1) O(h)
Which is…
O(n * ∑h=0..lg(n) h/2^h)
Now we use the useful fact that,
∑h=0..∞ h/2^h = 2
Which allows us to show that our running time is bound more tightly as O(n).
Heap-sort
Finally, we look at heap-sort. The heap-sort algorithm first constructs a max-heap which is a linear time operation, we then apply the max-heapify n-1 times as we repeatedly harvest the root node and restore the max-heap property using max-heapify (O(lg n) operation). So heap-sort is O(n lg n).
So, there you have it! Next time we’ll take a look at the venerable Quicksort algorithm.