#include<iostream> #define LEFT(i) (i<<2) #define RIGHT(i) ((i<<2)+1) using namespace std; void swap(int& small, int& big) { int temp = small; small = big; big = temp; } /* |把父节点和两个儿子节点做比较,把最大数的下标值存入largest |当父节点arr[root]比arr[leftchild]和ar[rightchild]时, |函数heap_adjust退出。下一次找最大数就是从左儿子节点开始的, |依次往下,比较父节点和子节点的大小。 */ void heap_adjust(int arr[], int root, int size) { int leftchild = LEFT(root); int rightchild = RIGHT(root); int largest; if (size < 1) return ; if ( leftchild <= size && arr[leftchild] > arr[root]) largest = leftchild; else largest = root; if ( rightchild <= size && arr[rightchild] > arr[root]) largest = rightchild ; /* | 上面已经把父节点arr[root]和左右儿子节点做大小比较(arr[leftchild],arr[rightchild]) | 当arr[leftchild]或arr[rightchild]大于父节点时,就交换他们的位置, | 此时这棵树就是最大堆 | |但还要确保以孩子节点为根的子树也是最大二叉树堆,所以依次比较,也就是递归比较 */ if ( largest != root ) { swap (arr[root], arr[largest]); heap_adjust(arr, largest, size); } } /* |序列中从arr[size/2+1]开始一直到arr[size-1] |在映射到完全二叉树的过程中都为叶子节点,即都为一颗独立的二叉树 |且都是只包含一个节点(即自己本身)的完全二叉树 | |所以在建树的时候,从arr[size/2 : 0]反向建树, |这样可以确保在对构建完整的二叉树从上至下,从左至右,所遵循的次序 |与序列中从0 -> (size-1)的循序是对应的。 */ void build_heap(int arr[], int size) { for (int i = size/2; i >= 0; i-- ) heap_adjust(arr, i, size); } /* |首先调用build_heap()构建一个最大堆,映射到二叉树就是: |映射每一棵二叉树上,父节点永远都是大于或等于子节点的。 | |二叉树构建完成后,我们知道arr[1]永远是整棵树中最大的数 |所以把arr[1]和arr[last]交换,也就是把arr[1]这个最大数放到序列队位 | |此时显然只需要比较前面last-1个数,也就是size -=1 |然后在剩余的last-1个节点中把次大树放到size-2的位置,也就是对应序列中倒数第二,次大数的位置 | |依次迭代... | |直到还剩最后两个数,进行最后依次比较。 | |由于每个函数都是传递的引用,所以对应大小次序的调整都直接是改变序列的。 |也就达到了排序的目的。 */ void heap_sort(int arr[], int size) { build_heap(arr, size); /* |这里last>=2是因为在heap_adjust()中比较最后两个数的大小就可以 |而不需要把最后一个数自身与自身进行比较。 |显然这样减少了比较次数和函数调用的次数 */ for ( int last = size; last >= 2; last--) { swap(arr[last], arr[0]); size -= 1; heap_adjust(arr, 0, size); } } //创建最大堆 int main() { const int size = 10; int iarray[size] = {15,3,4,9,25,60,87,88,92,5}; build_heap(iarray,size-1); heap_sort(iarray, size-1); for (int i = 0; i < size; i++ ) cout << iarray[i] << " "; cin.get(); return 0; }