1 //goal: heap sort 2 //time: 9/7/2014 3 //author: zrss 4 //reference: introduction to algorithms 5  6 #include <cstdio> 7 #include <cstring> 8  9 #define MAX_DATA 1010 11 class MaxHeap {12 public:13     MaxHeap(int *data, int size);14 15     void heap_sort(void); //堆排序，升序16 17     void output(void);18 19 private:20     void max_heapify(int i, int size); //使以i为根的子树成为最大堆，假设i左右子树均为最大堆21     void build_maxheap(int size); //自底向上使用max_heapify调整，建堆22 23 private:24     int size;25     int array[MAX_DATA]; //从下标0开始存储26 };27 28 MaxHeap::MaxHeap(int *data, int size):size(size) {29     if (size > MAX_DATA)30         return;31 32     memcpy(array, data, sizeof(int) * size);33 }34 35 void MaxHeap::max_heapify(int i, int size) {36     bool check = true;37 38     while (check) {39         int l = (i << 1) + 1;40         int r = l + 1;41 42         int largest = i;43 44         //与子节点比较45         if (l < size && array[l] > array[i])46             largest = l;47 48         if (r < size && array[r] > array[largest])49             largest = r;50 51         if (largest != i) {52             int temp = array[largest];53             array[largest] = array[i];54             array[i] = temp;55 56             i = largest; //从被交换的子节点位置继续调整57         }58         else59             check = false; //父节点不小于子节点，满足最大堆性质，停止调整60     }61 }62 63 void MaxHeap::build_maxheap(int size) {64     int leaf_start_index = size >> 1; //后续元素为叶子节点65 66     //从第一个父节点开始调整67     for (int i = leaf_start_index - 1; i >= 0; --i)68         max_heapify(i, size);69 }70 71 void MaxHeap::heap_sort(void) {72     int cur_size = size;73 74     while (cur_size > 1) {75         //调整成堆76         build_maxheap(cur_size);77 78         //将最大值与堆末尾元素交换79         int temp = array[cur_size - 1];80         array[cur_size - 1] = array[0];81         array[0] = temp;82 83         --cur_size;84     }85 }86 87 void MaxHeap::output(void) {88     for (int i = 0; i < size; ++i)89         printf("%d ", array[i]);90 }