在具体讨论堆排序法之前，先讨论这样一个问题：在一棵具有n个结点的完全二叉树[用一维数组H（1:n）表示]中，假设结点H(m)的左右子树均为堆，现要将以H(m)为根结点的子树也调整为堆。这是调整建堆的问题。
例如：假设图a是某完全二叉树的一棵子树。显然，在这棵子树中，根结点47的左、右子树均为堆。现在为了将整个子树调整为堆，首先将根结点47与其左、右子树的根结点值进行比较，此时由于左子树根结点91大于右子树根结点53，且它又大于根结点47，因此，根据堆的条件，应将元素47与91交换，如图b所示。经过这一次交换后，破坏了原来左右子树的堆结构，需要对左子树再进行调整，将元素85与47进行交换，调整后的结果如图c所示。
由这个例子可以看出，在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过
程一直做到所有子树均为堆为止。
有了调整建堆的算法后，就可以将一个无序列建成为堆。 堆排序的方法。略
堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为：
nlogn
2
小结：重点
查找
在最坏情况下，二分查找只需要比较log2n次， 在最坏情况下，顺序查找则需要比较n次。
交换类排序
冒泡排序法，在最坏情况下，需要比较n(n-1)/2次。
即O(n2)
快速排序法，在最坏情况下，需要比较n(n-1)/2次。 即O(n2) 平均时间： O(nlog2n)
插入类排序
简单插入排序法，在最坏情况下，需要比较n(n-1)/2次。 即O(n2)
希尔排序法，在最坏情况下，需要比较n1.5=n3/2= nn次。
选择类排序
在最坏情况下，简单选择排序法需要比较n(n-1)/2次。 在最坏情况下，堆排序需要比较的次数为：nlog2n