12,242,492 members (64,693 online)
Tip/Trick
alternative version

18.1K views
14 bookmarked
Posted

# Heap Data Structure and Heap Sort

, 3 Mar 2014 CPOL
 Rate this:
Simple approach to heap data structure and heapsort, using C and Lua

## Introduction

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

C, and Lua code is provided (C++ has library functions for this task).

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

## The Heap Data Structure

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.

We can draw, more generally, the heap this way

and state its properties in the concise form:

hk >= h2k+1
hk >= h2k+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 (h7>= h15, h7>= h16) 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'.

##### 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:

// The sift function:
// 'sifts down' the a[l] item until heap properties are restored
// ARGS:
//  a[] (INOUT) the array  (where a[l+1], a[l+2] .. a[size-1] is a partial heap)
//  size (IN) number of items of a
//  l (IN) index of the item inserted into the heap

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; // sift
}
a[i] = x;
}

The make_heap function is as follows:

// makes the heap using the R.W.Floyd's algorithm
// ARGS:
//  a[] (INOUT) the array wherein the heap is created
//  size (IN) the size of the array

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:

--// sifts the a[k] item in the a[k+1], a[k+2], .., a[r] partial heap
--//
--// REMARKS
--// if r is not provided then r = #a

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:

--// makes a in-place heap in a table using the R.W.Floyd's algorithm

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

--// sorts in-place the table 'a'
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

## History

• 28 Feb 2014 - First release

## Share

 Software Developer (Senior) AEM S.p.A. Italy

Debugging? Klingons do not debug. Our software does not coddle the weak. Bugs are good for building character in the user.
-- The Klingon programmer

Beelzebub for his friends [^].

## You may also be interested in...

 First Prev Next
 Very well written YvesDaoust10-Mar-14 4:55 YvesDaoust 10-Mar-14 4:55
 Re: Very well written CPallini21-Mar-14 11:40 CPallini 21-Mar-14 11:40
 thanks for this very good explanation :-) Matth Moestl3-Mar-14 12:57 Matth Moestl 3-Mar-14 12:57
 Re: thanks for this very good explanation :-) CPallini4-Mar-14 8:06 CPallini 4-Mar-14 8:06
 My vote of 5 Mika Wendelius2-Mar-14 5:31 Mika Wendelius 2-Mar-14 5:31
 Re: My vote of 5 CPallini2-Mar-14 7:15 CPallini 2-Mar-14 7:15
 My vote of 5 Skond2-Mar-14 0:55 Skond 2-Mar-14 0:55
 Re: My vote of 5 CPallini2-Mar-14 3:47 CPallini 2-Mar-14 3:47
 Last Visit: 31-Dec-99 19:00     Last Update: 30-Apr-16 1:08 Refresh 1