Click here to Skip to main content
13,045,387 members (79,662 online)
Click here to Skip to main content
Add your own
alternative version


15 bookmarked
Posted 28 Feb 2014

Heap Data Structure and Heap Sort

, 3 Mar 2014
Rate this:
Please Sign up or sign in to vote.
Simple approach to heap data structure and heapsort, using C and Lua


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

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:

sift down of the top node

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

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'.

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

building the heap by sifting down left side items

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:

// 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])
    if (x >= a[j])
    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)
    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
--// 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
    if x >= a[j] then break end
    a[i]  = a[j]
    i = j
    j = 2* i
  a[i] = x

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

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)

end of the sift down operation

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


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];
    a[0] = a[r];
    a[r] = tmp;
    sift(a, r,0);

Heap Sort Lua Code

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



  • 28 Feb 2014 - First release


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Software Developer (Senior) AEM S.p.A.
Italy 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...

Comments and Discussions

QuestionVery well written Pin
YvesDaoust10-Mar-14 3:55
memberYvesDaoust10-Mar-14 3:55 
AnswerRe: Very well written Pin
CPallini21-Mar-14 10:40
mvpCPallini21-Mar-14 10:40 
Questionthanks for this very good explanation :-) Pin
Matth Moestl3-Mar-14 11:57
professionalMatth Moestl3-Mar-14 11:57 
AnswerRe: thanks for this very good explanation :-) Pin
CPallini4-Mar-14 7:06
mvpCPallini4-Mar-14 7:06 
GeneralMy vote of 5 Pin
Mika Wendelius2-Mar-14 4:31
mentorMika Wendelius2-Mar-14 4:31 
GeneralRe: My vote of 5 Pin
CPallini2-Mar-14 6:15
mvpCPallini2-Mar-14 6:15 
GeneralMy vote of 5 Pin
Skond1-Mar-14 23:55
memberSkond1-Mar-14 23:55 
GeneralRe: My vote of 5 Pin
CPallini2-Mar-14 2:47
mvpCPallini2-Mar-14 2:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170713.1 | Last Updated 3 Mar 2014
Article Copyright 2014 by CPallini
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid