[算法笔记]堆排序（续）

　　上一篇有关堆排序的源码是从STL标准库中抽出来，但是源码有点让我混乱。最近闲来无事，再写一篇有关堆排序的博客，并附上简单的过程描述。

　　（参考书籍：《算法引论 —— 一种创造性方法》 4.7和6.4.5节）

　　堆排序最坏情况下的运行时间是O(n log n)。堆排序中建堆方式有两种：

　　1. 自顶向下建立大根堆。简单点说，就是从无到有插入元素到堆中。这样可以有效地维护了大根堆的性质，即大根堆是由满足大根堆性质的子堆构成。

　　2. 自底向上建立大根堆。一般都是从堆存储数组的一半的位置开始递减比较。需要注意的是，在每次比较后，需要调整子堆来满足大根堆的性质。有点类似于从建好的大根堆中移除元素之后的调整。（这种方式参考《数据结构（C语言版）》严蔚敏，吴伟民著的10.4.3节）

　　通过上述资料会发现，自顶向下建立大根堆的方式要比自底向上建立大根堆的方式简单。这里使用的是第一种方式：

 1 void build_heap( int heap[], int current_size )
 2 {
 3     int start = 0;
 4 
 5     while ( start < current_size - 1 )
 6     {
 7         // start在insert_to_heap函数会发生变化      
 8         insert_to_heap( heap, &start, start + 1, heap[start] );
 9     }
10 }

　　在建立堆之后，堆排序的处理：只需要将大根堆中的最大值（heap[0]）从堆中移除，并将其插入到数组的末尾（升序方式）。

 1 void heap_sort( int heap[], int current_size )
 2 {
 3     int i = current_size - 1;
 4     int j = current_size;
 5 
 6     build_heap( heap, current_size );
 7     while ( j )
 8     {
 9         int data = remove_max_from_heap( heap, &j );
10         heap[i] = data;
11         --i;
12     }
13 }

　　完整的源码：

  1 #include <stdio.h>
  2 #include <assert.h>
  3 
  4 void swap_value( int heap[], int lhs, int rhs )
  5 {
  6     int tmp = heap[lhs];
  7     heap[lhs] = heap[rhs];
  8     heap[rhs] = tmp;
  9 }
 10 
 11 /** @*current_size: 表示heap中已经存在的元素个数。
 12  ** @heap_size：表示heap的最大容量是多少
 13  */
 14 void insert_to_heap( int heap[], int *current_size,
 15                      int heap_size, const int value )
 16 {
 17     int child = *current_size;
 18     int parent = 0;
 19 
 20     assert( *current_size < heap_size );
 21     heap[child++] = value;
 22     parent = child / 2;
 23     while ( parent >= 0 )
 24     {
 25         if ( heap[child] > heap[parent] )
 26         {
 27             swap_value( heap, child, parent );
 28             child = parent;
 29             parent /= 2;
 30         }
 31         else
 32             parent = -1;
 33     }
 34     *current_size += 1;
 35 }
 36 
 37 int remove_max_from_heap( int heap[], int *current_size )
 38 {
 39     int result = 0;
 40     int child = 0;
 41     int parent = 0;
 42 
 43     if ( *current_size == 0 )
 44     {
 45         printf( "remove_max_from_heap: the heap is empty.
" );
 46         return -1;
 47     }
 48 
 49     result = heap[0];
 50     swap_value( heap, 0, *current_size - 1 );
 51     --*current_size;
 52     child = 1;
 53     while ( child <= *current_size - 1 )
 54     {
 55         if ( child < *current_size - 1
 56             && heap[child] < heap[child + 1] )
 57         {
 58             child += 1;
 59         }
 60 
 61         if ( heap[child] > heap[parent] )
 62         {
 63             swap_value( heap, child, parent );
 64             parent = child;
 65             child *= 2;
 66         }
 67         else
 68         {
 69             child = *current_size;
 70         }
 71     }
 72 
 73     return result;
 74 }
 75 
 76 void build_heap( int heap[], int current_size )
 77 {
 78     int start = 0;
 79 
 80     while ( start < current_size - 1 )
 81     {
 82         insert_to_heap( heap, &start, start + 1, heap[start] );
 83     }
 84 }
 85 
 86 void heap_sort( int heap[], int current_size )
 87 {
 88     int i = current_size - 1;
 89     int j = current_size;
 90 
 91     build_heap( heap, current_size );
 92     while ( j )
 93     {
 94         int data = remove_max_from_heap( heap, &j );
 95         heap[i] = data;
 96         --i;
 97     }
 98 }
 99 
100 int main()
101 {
102     int heap[] = { 78, 58, 87, 62, 92, 332, 55, 40, 75, 146 };
103     int heap_size = sizeof(heap) / sizeof(int);
104     int i = 0;
105 
106     heap_sort( heap, heap_size );
107     while ( i < heap_size )
108     {
109         printf( "%d ", heap[i++] );
110     }
111 
112 
113     return 0;
114 }

View Code

[算法 笔记]堆排序（续）

[算法笔记]堆排序（续）