This is an attempt to introduce beginners to the heap data structure and the heap sort algorithm.

Wirth's book [1] is the inspiration and the reference for this article.

A heap is a kind of binary tree having this property: every parent value is greater than (or equal to) its children's

so that 'the patriarch' (the root) holds the maximum value.

and state its properties in the concise form:

h_{k }>= h_{2k+1}

h_{k }>= h_{2k+2}

#####

##### 1 - heap properties

#####

Now, suppose we have the partial heap

where the top node is missing. If we add an arbitrary value, say 4, the resulting tree is no more a heap,

because the top value is less than its childrens.

However, there is an ingenious way to rearrange the tree in order to get back a heap. Its called *sift down* of the item and it is shown in the following pictures:

##### 2 - sift down of the item, until the heap is restored

That is, if the parent value is less than any of its children, it is swapped with the greatest child, repeatedly.

##

## Building the Heap in an Array

It is worth noting we can host a heap inside an array.

###

provided the heap properties (1) hold.

### The Algorithm

Starting with an assigned array, we may rearrange it to host an heap, in place, using an algorithm due to *R.W.Floyd* (see [1]).

Suppose we have the following, arbitrarily assigned, array

The right half side (the blue marked side) is *already arranged as the bottom row of a heap, *because its items have no children: consider, for instance the first 'blue' item, having value 24. Its index is 7, hence the heap properties for such item (h_{7}>= h_{15}, h_{7}>= h_{16}) are automatically satisfied, because there are no items with index 15 or 16 in the array.

So the 'blue side' is our partial heap and we can proceed with heap construction by repeatedly sifting down the items of the 'red side'.

##### 3 - sifting down the first 'red' (left side) item of the array

##### 4 - partial heap is augmented, after having sifted down the item

##### 5 - final steps of in place heap construction

I hope these drawings help to understand the algorithm, anyway we cannot run pictures, so it is time to show some code.

## The C Code

The `sift`

function is as follows:

void sift(int a[], int size, int l)
{
int i,j, x;
i = l;
j = 2*i+1;
x = a[i];
while (j < size)
{
if ( j <size - 1)
if ( a[j] < a[j+1])
++j;
if (x >= a[j])
break;
a[i] = a[j];
i = j;
j = 2*i + 1; }
a[i] = x;
}

The `make_heap`

function is as follows:

void make_heap(int a[], int size)
{
int l = size / 2;
while (l)
{
--l;
sift(a, size, l);
}
}

That's all.

## The Lua Code

The `sift`

function is as follows:

--------
local function sift(a, k, r)
r = r or #a
local i = k
local j = 2 * i
local x = a[i]
while j <= r do
if j < r then
if a[j] < a[j+1] then j = j + 1 end
end
if x >= a[j] then break end
a[i] = a[j]
i = j
j = 2* i
end
a[i] = x
end

The `make_heap`

function is as follows:

--
function make_heap(a)
local l = math.floor(#a/2) + 1
while l > 1 do
l = l - 1
sift(a,l)
end
end

## Heap Sort

Heap sort is one of the nice applications of the data structure and algorithms depicted so far.

Suppose we have an assigned, unsorted array

our task is: sort it in descending order.

We already know how to *make a heap* with it

so that the maximum value (29) is now the first item of the array (or, in other words, is on the top of the heap).

We can remove such maximum value (storing it in a safe place) and rearrange the remaining items in order to regain a heap (to obtain another 'maximum', that is the successive value of the sorted sequence).

It turns out the safe place for storing the maximum value is the last item of the array. As matter of fact, we *swap *the first and last item.

Now we have:

- The maximum value in its own safe place (grayed, on the right side of the array)
- A partial heap to fix (the blue items)
- An item to sift down (the read one)

Here, we have back a (one item shorter) heap and can proceed with next items:

Done!

Well, there is just a little problem: our target was: sort it in *descending* order. Hence, we either re-state it according to our results ( ) or, better, change the algorithm to obtain the opposite sort order. It turns out that just reversing the operators (while comparing array items in the `sift`

function) does the trick (task left to the reader) .

## Heap Sort C Code

void heapsort(int a[], int size)
{
int l = 0, r = size;
make_heap(a, size);
while ( r > 1)
{
int tmp = a[0];
--r;
a[0] = a[r];
a[r] = tmp;
sift(a, r,0);
}
}

## Heap Sort Lua Code

--function heapsort(a)
make_heap(a)
local l,r
l = 1
r = #a
while r > 1 do
local x
x = a[1]
a[1] = a[r]
a[r] = x
r = r - 1
sift(a,l,r)
end
end

## References

## History

- 28 Feb 2014 - First release