自己动手写算法.Sort.HeapSort

Heap Sort Algorithm

heap-sort uses max heap data structure to sort a sequence. The steps are:

• We need construct a max heap in place firstly, so that we can make sure that the bigest value locates on the first position of the heap.
• Swap the top value with the last value of the sequence, and shrink the size to nSize-1, and reconstruct the max heap.
• Swap loopsly and the sequence will be sorted.

The key issue is how to present a max heap data structure by an array.

 

1. #define LEFT_CHILD_INDEX(idx) (idx*2 + 1)
2. #define RIGHT_CHILD_INDEX(idx) (idx*2 + 2)
3. #define PARENT_INDEX(idx) (idx-1)/2
5. /*
6. Given a max-heap, if we changed a value at idx, we should make sure
7. that all its children are not bigger than it.
8. */
9. void max_heapify( const int idx, int arr[], const int nSize )
10. {
11.     int nCur = idx;
12.     int nLeft = LEFT_CHILD_INDEX(nCur);
13.     int nRight = RIGHT_CHILD_INDEX(nCur);
15.     if( nRight < nSize-1 )
16.     {
17.         if( arr[nCur] < arr[nRight] )
18.         {
19.             std::swap( arr[nCur], arr[nRight] );
20.             max_heapify(nRight, arr, nSize);
21.         }
22.     }
24.     if( nLeft < nSize-1 )
25.     {
26.         if( arr[nCur] < arr[nLeft] )
27.         {
28.             std::swap( arr[nCur], arr[nLeft] );
29.             max_heapify(nLeft, arr, nSize);
30.         }
31.     }
34. }
36. /*
37. a non complete binary tree has (nSize+1)/2 children
38. */
39. void build_max_heap(int arr[], const int nSize)
40. {
41.     int nCount = nSize - (nSize+1)/2;
42.     for(int i=0; i<nCount; ++i)
43.     {
44.         max_heapify(i, arr, nSize);
45.     }
46. }
48. /*
49. Build a max heap firstly, so the first one is the biggest one
50. Swap with the last one, rebuild the max heap, but ignoring the last one
51. */
52. void SortHeap::sort(int arr[], const int nSize)
53. {
54.     ALog::print(_T("# Heap Sort: "));
55.     ALog::print(arr, nSize);
57.     build_max_heap(arr, nSize);
58.     ALog::print(arr, nSize);
59.     for( int i=nSize-1; i>1; --i )
60.     {
61.         std::swap(arr[0],arr[i]);
62.         max_heapify(0, arr, i);
63.         ALog::print(arr, nSize);
64.     }
65. }
67. void SortHeap::test()
68. {
69.     int arr[] = { 2, 9, 3, 7, 8, 6, 4, 5, 0, 1};
70.     const int nSize = sizeof(arr)/sizeof(int);
71.     SortHeap::sort(arr, nSize);
72. }

 

The test result:

 

# Heap Sort: 

2 9 3 7 8 6 4 5 0 1

================
9 8 6 7 3 4 2 5 0 1
 8 7 4 6 3 2 1 5 0 9
 7 6 2 4 3 1 0 5 8 9
 6 5 2 4 3 1 0 7 8 9
 5 4 0 3 2 1 6 7 8 9
 4 3 0 1 2 5 6 7 8 9
 3 2 0 1 4 5 6 7 8 9
 2 1 0 3 4 5 6 7 8 9
 0 1 2 3 4 5 6 7 8 9