新疆建设工程云网站操作具体流程/上海百度整站优化服务

基本思想

创建堆：升序—>大堆，降序—>小堆

执行如下步骤，直到数组为空：

• 把堆顶array[0]元素和当前最堆的最后一个元素交换
• 堆元素个数减1
• 由于第1步后根节点不再满足最堆定义，向下调整根结点

代码实现

void HeapAdjustDown(int* array, size_t n,int parent) //向下调整
{int temp = 0;int child = parent * 2 + 1;//左孩子while (child < n){if (child + 1 < n && array[child] < array[child + 1]){++child;}if (array[child]>array[parent]){temp = array[child];array[child] = array[parent];array[parent] = temp;parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* array, size_t n) //堆排序
{assert(array);for (int i = (n - 2) / 2; i >= 0; --i){HeapAdjustDown(array, n, i);}size_t end = n - 1;while (end > 0){int temp = 0;temp = array[0];array[0] = array[end];array[end] = temp;HeapAdjustDown(array, end, 0);--end;}
}

时间复杂度及稳定性

把一棵完全二叉树调整为堆，以及每次将堆顶元素交换后进行调整的时间复杂度均为O( log2 n)，
所以堆排序的时间复杂度为：O(n log 2 n)
稳定性：不稳定