heap sort

This is a discussion on heap sort within the C Programming forums, part of the General Programming Boards category; Hi,people! I was looking through adjustment of heap but the explanation is too difficult for me. I'll appreciate if somebody ...

  1. #1
    Registered User
    Join Date
    Jun 2002
    Posts
    3

    Question heap sort

    Hi,people!

    I was looking through adjustment of heap but the explanation is too difficult for me.
    I'll appreciate if somebody can explane and show easy and clear model of heap sorting.

    Thanks!

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    A heap is a structure where items are stored in an array in such a way so that each item is guaranteed to be larger than the items at two other specific locations. Each of those items are also larger than two more, and so on. It's a binary structure compressed into a linear array:
    Code:
             X
          /     \
        T         O
       / \       / \
      G   S     M   N
     /\   /\   /
    A  E R  A I
    
    1 2 3 4 5 6 7 8 9 10 11 12
    X T O G S M N A E R  A  I
    The heapsort is a method of building a heap and then removing the largest element repeatedly until the data is sorted. Here's the basic idea:
    Code:
    #include <stdio.h>
    
    #define less(a, b) ((a) < (b))
    
    static void exchange ( int *a, int *b )
    {
      int t = *a;
      *a = *b;
      *b = t;
    }
    
    static void fixDown ( int *a, int k, int N )
    {
      int j;
      while ( 2 * k <= N ) {
        j = 2 * k;
        if ( j < N && less ( a[j], a[j+1] ) )
          j++;
        if ( !less ( a[k], a[j] ) )
          break;
        exchange ( &a[k], &a[j] );
        k = j;
      }
    }
    
    static void heapsort ( int *a, int l, int r )
    {
      int k, N = r - l + 1;
      int *pq = a + l - 1;
      for ( k = N / 2; k >= 1; k-- )
        fixDown ( pq, k, N );
      while ( N > 1 ) {
        exchange ( &pq[1], &pq[N] );
        fixDown ( pq, 1, --N );
      }
    }
    
    int main ( void )
    {
      int i;
      int a[10] = {8,3,9,1,0,5,9,3,6,4};
      heapsort ( a, 0, 9 );
      for ( i = 0; i < 10; i++ )
        printf ( "%d ", a[i] );
      printf ( "\n" );
      return 0;
    }
    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  2. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  3. Heap Sort
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-18-2005, 01:53 PM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21