如题所述
如果是最大堆，那么堆顶元素就是最大的。并且它是一种二叉树的形式。因此它的左右子树也是一个最大堆。也就说左子树和右子树的根都是当前子树中最大的元素。堆排序的原理就是维护一个最大堆。可以详见数据结构书，那段代码写的相当简洁易懂。初始化堆时，要弄明白为什么是更新一半的元素。你可以在纸上画一画，对每一个元素从二叉树上从1开始标号。会发现标号为1 ， 2，..n/2 的结点刚好可以覆盖二叉树的所有路径，并且是从 n/2 到 1 去更新堆，这样的话就可以构成一个初始化的最大堆。每次更新最大堆时，都是沿着左右子树的路径一次更新，要左右子结点较大的元素往上移动，知道更新的元素大于左右子树的结点值。那么就成了一个新的最大堆。复杂度就是二叉树数的层数。即每次更新复杂度是log(n).
温馨提示：答案为网友推荐，仅供参考
第1个回答 2012-11-28
如果是最大堆，那么堆顶元素就是最大的。并且它是一种二叉树的形式。因此它的左右子树也是一个最大堆。也就说左子树和右子树的根都是当前子树中最大的元素。堆排序的原理就是维护一个最大堆。可以详见数据结构书，那段代码写的相当简洁易懂。初始化堆时，要弄明白为什么是更新一半的元素。你可以在纸上画一画，对每一个元素从二叉树上从1开始标号。会发现标号为1 ， 2，..n/2 的结点刚好可以覆盖二叉树的所有路径，并且是从 n/2 到 1 去更新堆，这样的话就可以构成一个初始化的最大堆。每次更新最大堆时，都是沿着左右子树的路径一次更新，要左右子结点较大的元素往上移动，知道更新的元素大于左右子树的结点值。那么就成了一个新的最大堆。复杂度就是二叉树数的层数。即每次更新复杂度是log(n).
