Yuhang He's Blog

Some birds are not meant to be caged, their feathers are just too bright.

Heap sort algorithm

Heap Sort fits for data insertion and data sorting at the same time. It tries to store data in a complete binary tree, ensuring the nonleaf node is larger or smaller than the left/right leaf node. The advantage of storing data into complete binary tree is that the largest or smallest value always pop out in to root node. So, after forming the complete binary tree, we fetch the root value and store it in the first or the last location in a[N], and replace the root value with the corresponding value in a[N].

There are some important issues during implementation: 1. for the nonleaf node a[i], its left-leaf node is a[2*i + 1], and the right-leaf node is a[2*i + 2]. 2. if the length of data to sort is N, the leaf node number is int(N/2.0 + 0.5).

First, we need to write the heap adjust code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void HeapAdjust( int a[], int node_tmp, int n ) // n is the data number, node_tmp is the temporary nonleaf node.
{
  int change_index = 0;
  int val_tmp = 0;
  while(  2*node_tmp + 1 < n ) //its left leaf exists
  {
    change_index = 2*node_tmp + 1;
    if( change_index + 1 < n && a[j] < a[j+1] ) //if right leaf is larger than left leaf;
      change_index++;
    if( a[node_tmp] < a[change_index] )
    {
      val_tmp = a[node_tmp];
      a[node_tmp] = a[change_index];
      a[change_index] = val_tmp;
      node_tmp = change_index;
    }
    else
      break;
  }
}

Second, we have to sort the data with Heap Sort in an iterative way.

1
2
3
4
5
6
7
8
9
10
11
12
13
void HeapSort( int a[], int n )
{
  int t = 0; int j = 0;
  for( int i = n/2 - 1; n > 0; --i )
    HeapAdjust( a, i, n );
  for( int i = n - 1; i > 0; --i )
  {
    t = a[0];
    a[0] = a[i];
    a[i] = t;
    HeapAdjust( a, 0, i );
  }
}