排序算法第六篇——堆排序

一、优先队列（堆）

优先队列包括两种操作的数据结构，插入和删除最小者。

二叉堆的结逻辑结构是一个完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右排列。

二叉堆的物理结构是一个数组，元素存放从下标为1的位置开始。因为这样子实现的话，对于数组中的某一个位置i的元素，在下标不越界的情况下（也就是说该节点有孩子的情况下），其左孩子在位置2i上，有孩子在2i+1上。

二、插入操作

对于堆的插入操作实现，一般使用的策略是上滤（percolate up）策略。上滤操作是只先将要插入的元素插入到最后位置，然后与其父节点比较，如果比父节点还要小，说明该节点放在该位置不符合堆序性质（堆序性质是指一个父节点的值小于两个孩子的值，此时为小堆，如果父节点的值大于两个孩子的值，此时为大堆）。所以将该节点与父节点交换，使符合堆序性质，交换之后，再与新插入元素的父节点比较，知道整个堆符合堆序性质。

三、删除最小者

删除最小者是针对小堆而言的，对小堆来说，最小者始终在根节点，在数组中也就是第一个位置的元素。删除最小者一般使用的策略是下滤（percolate down），下滤是指将根节点删除，然后将最后一个元素的值放到根节点的位置，然后再调整堆，使堆符合堆序性质。

调整堆的过程：

1、先判断其是否有右孩子，如果有右孩子，则必定有左孩子。

判断左右孩子的值是否均大于该节点，如果不是，则与孩子中的最小者交换。以此类推，直到找到结点和合适位置。

2、没有右孩子，只有左孩子

判断右孩子的值是否大于该节点，如果不是，交换两者的位置，以此类推，知道找到结点的合适位置。

3、叶节点，无左右孩子

不用再进行判断，该位置比为该节点的合适位置。

Java源代码如下：

<span style="font-family: SimSun; font-size: 18px;">package ljp.sort.heap;

public class HeapSort {
	private int[] list;
	private int length;

	// 构造函数，初始化数组
	public HeapSort() {
		list = new int[11];
		list[0] = 0;
		length = 0;
		for (int i = 1; i < list.length; i++) {
			list[i] = (int) (Math.random() * 1000);
		}
		for (int i = 1; i < list.length; i++) {
			System.out.print(list[i] + " ");
		}
		System.out.println();
		System.out.println("建堆过程：");
		CreateHeap();
	}

	private void CreateHeap() {
		// 执行length-1次上滤操作
		for (int i = 1; i < list.length; i++) {
			PercolateUp(i);
			length++;
			for (int j = 1; j <= i; j++) {
				System.out.print(list[j] + " ");
			}
			System.out.println();
		}
	}

	// 上滤——将要插入的元素放到最后位置
	// 然后与其父结点比较，如果比父结点小，则将该结点与父节点交换
	// 以此类推，直到找到最佳位置
	private void PercolateUp(int i) {
		list[0] = list[i];
		while (i > 0 && list[0] < list[i / 2]) {
			list[i] = list[i / 2];
			i = i / 2;
		}
		list[i] = list[0];
	}

	// 下滤 ——选择删除结点的两个孩子中的较小者放在删除结点的位置
	// 到达叶子结点之后，将最后一个元素放到叶子结点
	// 然后从该叶子结点进行上滤操作
	private void PercolateDown() {
		System.out.print(list[1]+" ");
		int i = 1;
		while (true) {
			int lchild = i * 2;
			int rchild = i * 2 + 1;
			// 有两个孩子
			if (rchild < length + 1
					&& (list[length] > list[lchild] || list[length] > list[rchild])) {
				if (list[lchild] < list[rchild]) {
					list[i] = list[lchild];
					i = lchild;
				} else {
					list[i] = list[rchild];
					i = rchild;
				}
			} else if (lchild < length + 1 && list[length] > list[lchild]) {// 只有左孩子
				list[i] = list[lchild];
				i = lchild;
				break;
			} else {// 叶节点，没有孩子
				break;
			}
		}
		list[i] = list[length--];
	}

	public void display() {
		System.out.println("排序：");
		// 执行length-1次下滤操作
		for (int i = 1; i < list.length; i++) {
			PercolateDown();
		}
		System.out.println();
	}

	public static void main(String[] args) {
		HeapSort heapsort = new HeapSort();
		heapsort.display();
	}

}
</span>

运行结果：

297 35 658 170 208 821 810 732 904 884
建堆过程：
297
35 297
35 297 658
35 170 658 297
35 170 658 297 208
35 170 658 297 208 821
35 170 658 297 208 821 810
35 170 658 297 208 821 810 732
35 170 658 297 208 821 810 732 904
35 170 658 297 208 821 810 732 904 884
排序：
35 170 208 297 658 732 810 821 884 904