堆排序详解（JAVA版）

package com.hsit.heap;import java.util.Scanner;/*** * &＃64;author Colo* &＃64;version 创建时间&＃xff1a;2011-11-1 上午11:44:10*/
public class Heap {private int[] data;/*输入数组元素,数组下标从1开始*/public void input() {System.out.println("请输入数组大小");Scanner scanner &＃61; new Scanner(System.in);int n &＃61; scanner.nextInt();data &＃61; new int[n &＃43; 1];System.out.println("输入数组元素");for (int i &＃61; 1; i <&＃61; data.length-1; i&＃43;&＃43;) {data[i] &＃61; scanner.nextInt();}System.out.println("输入完成");}/*** 调整堆&＃xff0c;使其满足堆得定义* &＃64;param i* &＃64;param n*/public void adjust(int i, int n) {int child;for (; i <&＃61; n / 2; ) {child &＃61; i * 2;if(child&＃43;1<&＃61;n&&data[child] 0; i--)adjust(i, data.length-1);for (int i &＃61; data.length-1; i > 0; i--) {/*把根节点跟最后一个元素交换位置&＃xff0c;调整剩下的n-1个节点&＃xff0c;即可排好序*/swap(1, i);adjust(1, i - 1);}}public void swap(int i, int j) {int temp &＃61; data[i];data[i] &＃61; data[j];data[j] &＃61; temp;}public void print() {for (int i &＃61; 1; i

建堆

  如上&＃xff0c;首先第一步&＃xff0c;在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个&＃xff0c;将其下标存储在child中。如果A[i]已经就是最大的元素&＃xff0c;则程序直接结束。否则&＃xff0c;i的某个子结点为最大的元素&＃xff0c;将其&＃xff0c;即A[child]与A[i]交换&＃xff0c;从而使i及其子女都能满足最大堆性质。下标child所指的元素变成了A[i]的值&＃xff0c;会违反最大堆性质&＃xff0c;所以对child所指元素为根的子树重新调整。如下&＃xff0c;是此adjust的演示过程&＃xff08;下图是把4调整到最底层&＃xff0c;一趟操作&＃xff0c;但摸索的时间为LogN&＃xff09;&＃xff1a;

     由上图&＃xff0c;我们很容易看出&＃xff0c;初始构造出一最大堆之后&＃xff0c;在元素A[i]&＃xff0c;即16&＃xff0c;大于它的俩个子结点4、10&＃xff0c;满足最大堆性质。所以&＃xff0c;i下调指向着4,小于,左子14&＃xff0c;所以&＃xff0c;调用adjust&＃xff0c;4与其子&＃xff0c;14交换位置。但4处在了14原来的位置之后&＃xff0c;4小于其右子8&＃xff0c;又违反了最大堆的性质&＃xff0c;所以再递归调用adjust&＃xff0c;将4与8&＃xff0c;交换位置。于是&＃xff0c;满足了最大堆性质&＃xff0c;程序结束。

排序

以下是&＃xff0c;堆排序算法的演示过程&＃xff08;通过&＃xff0c;顶端最大的元素与最后一个元素不断的交换&＃xff0c;交换后又不断的调用adjust重新维持最大堆的性质&＃xff0c;最后&＃xff0c;一个一个的&＃xff0c;从大到小的&＃xff0c;把堆中的所有元素都清理掉&＃xff0c;也就形成了一个有序的序列。这就是堆排序的全部过程。&＃xff09;&＃xff1a;

上图中&＃xff0c;a->b&＃xff0c;b->c&＃xff0c;....之间&＃xff0c;都有一个顶端最大元素与最小元素交换后&＃xff0c;调用adjust的过程&＃xff0c;而要完成整个堆排序的过程&＃xff0c;共要经过O&＃xff08;n&＃xff09;次这样的adjust操作。所以&＃xff0c;才有堆排序算法的运行时间为O&＃xff08;n*lgn&＃xff09;。