Handout 37

Heap Sort

Heaps

A heap is a binary tree (not a binary search tree) with the following properties:

for every node, all nodes in all subtrees have data smaller than the data in that node
the tree is full and dense

Full and dense means that only the bottom level of the tree has gaps, and the gaps are all on the right.

Being dense means the linear array representation is the most appropriate. A linked representation would waste space.

A min-heap contains the minimum value as the root, a max-heap contains the maximum value as the root.

Here are some heaps of varying sizes

    2     2   2    2     2      2
   / \        |   / \   / \    / \
  3   7       3  3   7 3   7  3   7
 / \  |               /      / \
9   7 8              9      9   7

Priority Queue

A heap is a great data structure for implementing a priority queue, because

The next item to do (the item with the highest priority) is right at the top of the heap, i.e., at the root
Adding a new item takes at most log₂N swaps and compares which is better than the O(N) data transfers a sorted array would require.
Removing an item and updating the tree takes at most log₂N steps.

It also turns out we can use the routines for adding and removing items to create an N log₂N sort algorithm called heap sort.

Adding Data (min-heap)

The algorithm for adding data to a min-heap is simple, with one unintuitve aspect: we add an item to the bottom first then move it upwards, if necessary:

add a new data item to the next empty gap in the bottom of the tree
"walk" the data item up the tree, i.e., while the data is smaller than its parent, swap the item with its parent, and repeat, checking the data item with its new parent

Walking up the tree will take at most log₂N steps (compares and data transfers), because the tree is always balanced, so the height of the tree is log₂N.

Here's an example, based on inserting the values 5, 6, 4, 4, 7, 2

Initial tree:
```
    5
```
Insert 6, no need to swap.
```
    5
   /
  6
```

Insert 4, swap with root.

    5         4
   / \  to   / \
  6   4     6   5

Insert 4, swap once

    4         4
   / \       / \
  6  5  to  4   5
 /         /
4         6

Insert 7, no need to swap.
```
    4
   / \
  4   5
 / \
6   7
```

Insert 2, need to percolate up to root.

    4           4          2
   / \         / \        / \
  4   5  to   4   2 to   4   4
 / \  |      / \  |     / \  |
6   7 2     6   7 5    6   7 5

Deleting Data (min-heap)

Both uses of heaps (priority queues and heap sort) only need to delete the root, so that's the only case we'll consider here. Deleting is somewhat similar to adding in that we'll replaced the deleted root with another item from the tree and bubble it down. The algorithm is made only slightly more complex because we have two children to worry about instead of just one parent.

Remove the root.
Replace it with the rightmost item in the bottom level of the tree.
The new item is almost certainly in the wrong place because it's one of the larger data elements, but this keeps the heap full and dense.
If the new root has no children smaller than it is, we're done.
If it has just a left child that is smaller, swap it with the child and go back to step 2 with the left subtree.
If it has two children that are smaller, swap it with the smallest child and go back to step 2 with the affected subtree.

Note that

In choice 5, the child promoted is known to be smaller than the other child, so it must be the smallest item in the two subtrees. We don't need to bubble it down.

Walking down the tree will take at most log₂N steps (compares and data transfers). We may have to do three comparisons (parent with each child and child against child) but 3 log₂N is still O(log₂N).

Here's a sample case of removal of least element.

    2          ?          5          3          3
   / \        / \        / \        / \        / \
  3   4  to  3   4  to  3   4  to  5   4  to  4   4
 / \  |     / \  |     / \        / \        / \
6   4 5    6   4 5    6   4      6   4      6   5

Implementing Heaps

As mentioned above, heaps are best implemented using a linear array. The move up and down the tree are simple jumps around the array and the array is mostly filled. The only downside is that data has to be moved around, unless, of course, what we really have is an array of pointers to data, which is the best way to go with non-numeric data.

heap template implementation using an array

Some Tips on Array Implementation

Consider the following heap:

We can implement this heap as an array:

Index

0

1

2

3

4

5

6

Value

a

b

c

d

e

f

g

From any element in the array, we may find the elements parent by the relationship:

parent_index = (current_index - 1) / 2

We can the left and right children of any element by the relationships:

left_child_index = 2 * current_index + 1right_child_index = 2 * current_index + 2

sources include this and this and this