一些关于堆排序东西！

堆排序是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆一般都指的是二叉堆，它满足二个特性：

           1：父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

           2：每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

void heapify(int *a, int i, int len) { int left = 2 * i + 1;     // 左孩子结点下标 int right = 2 * i + 2;    // 右孩子结点下标 int max = i;     // 三个节点中最大元素的下标 if (left < len && a[left] > a[max]) max = left; if (right < len && a[right] > a[max]) max = right; if (max != i)   // 当前父节点不是所有结点中最大的元素，需要做调整 { swap (a, i, max); heapify (a, max, len);   // 调整被交换的结点 } }

堆排序函数：

void heapSort (int *a, int len) { // 建堆 int i; for (i = len/2 - 1; i >= 0; i--) { heapify (a, i, len); } // 排序 for (i = len-1; i > 0; i--) { swap (a, 0, i);       // 拿堆顶元素与队尾元素进行交换 len--;                // 找到一个最大元素以后堆大小减1 heapify (a, 0, len);  // 调整堆顶元素 } }