2堆排序 则每次选择出一个最大(或最小)的数据元素只需比较完全三 叉树的高度次,即lg2n次,则排序算法的时间复杂度就是 o( n). 堆的定义 堆分为最大堆和最小堆两种。定义如下: 设数组a中存放了n个数据元素,数组下标从0开始,如果当数 组下标2计1<m时有:l4]key2计+1keya[ikey≤a2i+1key); 如果当数组下标2计+2<n时有: ai. key≌a[2计+2key (a[]key≤a2i+2]key),则这样的数据结构称为最大堆(最小堆)2.堆排序 基本思想:把待排序的数据元素集合构成一个完全二叉树结构， 则每次选择出一个最大（或最小）的数据元素只需比较完全二 叉树的高度次，即log2 n次，则排序算法的时间复杂度就是 O(nlog2n)。 一、堆的定义 堆分为最大堆和最小堆两种。定义如下： 设数组a中存放了n个数据元素，数组下标从0开始，如果当数 组下标2i+1<n时有:a[i].key≥a[2i+1].key(a[i].key≤a[2i+1].key)； 如 果 当 数 组 下 标 2 i+2<n 时 有 : a[i].key≥a[2i+2].key (a[i].key≤a[2i+2].key)，则这样的数据结构称为最大堆(最小堆)