Click here to Skip to main content
Click here to Skip to main content

Heap Data Structure and Heap Sort

, 3 Mar 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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

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])
        ++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)

end of the sift down operation

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 ( Smile | :) ) 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

References

History

  • 28 Feb 2014 - First release

License

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

Share

About the Author

CPallini
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 [^].



Follow on   LinkedIn

Comments and Discussions

 
QuestionVery well written PinmemberYvesDaoust10-Mar-14 4:55 
AnswerRe: Very well written PinmvpCPallini21-Mar-14 11:40 
Questionthanks for this very good explanation :-) PinprofessionalMatth Moestl3-Mar-14 12:57 
AnswerRe: thanks for this very good explanation :-) PinmvpCPallini4-Mar-14 8:06 
GeneralMy vote of 5 PinmentorMika Wendelius2-Mar-14 5:31 
GeneralRe: My vote of 5 PinmvpCPallini2-Mar-14 7:15 
GeneralMy vote of 5 PinmemberSkond2-Mar-14 0:55 
GeneralRe: My vote of 5 PinmvpCPallini2-Mar-14 3:47 

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

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

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