堆排序原理以及实现

堆性质的简介

堆是以二叉树的形式存储的一种数据结构，常见的堆的使用方式主要包括：堆排序，优先队列的构造。堆主要分为最小堆与最大堆，最小堆的主要性质是根结点小于等于两个子结点的值，同理可得，最大堆的主要性质是根节点大于等于两个子节点的值。由于堆是一棵二叉树，所以根据堆的性质，堆可以看作是一棵完全二叉树。

堆的创建

从定理中可以看出，要想保持堆的基本性质关键点在于根节点与两个子结点之间的关系，我们从这个性质出发考虑如何来维护堆的基本性质。保证新插入的数据不会影响最大堆的性质。 public void maxHeap(int[] A,int i,int length){ int left = i*2 + 1; // 根结点的左孩子 int right = i*2 + 2; // 根结点的右孩子 int largest = i; // 如果存在左孩子，且左孩子大于插入结点的值 if(left < length && A[i] < A[left]){ largest = left; } // 如果存在右孩子，且右孩子大于插入结点的值 if(right < length && A[largest] < A[right]){ largest = right; } // 如果最大值不是当前插入的结点的值，交换两个结点之间的值 if(largest != i){ exchange(A, i, largest); maxHeap(A,largest,length); } } private void exchange(int[] A, int i, int largest) { A[i] = A[i] ^ A[largest]; A[largest] = A[i] ^ A[largest]; A[i] = A[i] ^ A[largest]; } 从程序中我们可以看出，对于新插入的结点在数组的第一个位置，首先比较其对应的左孩子与右孩子的值，将三个结点中值最大的设置为根结点，将要插入的结点与其交换位置。利用下标 largest，i 判断是否发生过交换，如果发生过交换，交换对应两个结点的值，利用递归的形式重复上面的步骤，未发生交换则退出。下图为交换的过程。 从上图我们可以很清楚的看到程序的比较过程。对于给定的数组A={4,1,3,2,16,9,10,14,8,7}，通过上面的比较我们可以看出，从第 A.length/2+1个元素到A.length个元素都为叶子结点。所以我们在建堆时直接可以从A.length/2 到第0个元素一次调用maxHeap()方法。具体程序如下所示。 public void buildMaxHeap(int[] A){ for(int i = A.length >> 1; i >= 0 ; i--){ maxHeap(A,i,A.length); } } 通过上面的几个程序，我们就可以建立一个堆了。

利用创建好的堆进行堆排序

主要的思路是，交换堆中第一个元素与最后一个元素（按数组中的下标作出选择），然后重新调用maxHeap()方法维护堆的结构。具体代码如下： // 堆排序 public void heapSort(){ // 考虑到堆是完全二叉树，所以可以考虑使用连续的数组存储二叉树的结点。 int a[] = {4,1,3,2,16,9,10,14,8,7}; // 建立最大堆 buildMaxHeap(a); System.out.println(Arrays.toString(a)); // 堆排序 int length = a.length; for(int i = 0; i+1 < length;){ exchange(a,i,--length); maxHeap(a,i,length); } System.out.println(Arrays.toString(a)); }

利用堆构造优先队列

我们先来看一下优先队列的定义，在算法导论中关于优先队列的定义是这样的：优先队列（priority queue） 是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有相关的值，称为关键字(key)。一个优先队列支持一下操作（最大优先队列）： 1、insert(S,x)：把元素x插入集合S中。这一操作等价于S=SU{x}。 2、maximum(S) ：返回S中具有最大关键字的元素。 3、extractMax(S) ： 去掉并返回S中具有最大关键字的元素。 4、increaseKey(S,x,k) ：将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字的值。 优先队列的应用有很多，其中一个就是共享计算机系统的作业调度。 下面让我们一起实现这几个方法。 insert(S,x)：把元素x插入集合S中。这一操作等价于S=SU{x}，因为涉及到扩充的问题，又因为数组不具有可扩充的特性，这里我假设每次申请多余的数组空间。 // 把元素x插入到集合A中 public void insert(int[] A,int x){ int i; // 遍历一遍数组，查找已存在数组的末尾下标 for(i = 0; i < A.length; i++){ if(A[i] == -1){ break; } } A[i] = Integer.MIN_VALUE; increaseKey(A,i,x); } maximum：返回S中具有最大关键字的元素，这个是容易实现的方法。 public int maximum(int[] A){ return A[0]; } extactMax(S) ： 去掉并返回S中具有最大关键字的元素，我们结合之前的maxHeap()方法，很容易想到如何实现这个方法。 // 返回最大优先队列中的最大元素并删除 public int extractMax(int[] A){ int max; int length = A.length-1; // 判断A数组中元素的个数 if(A.length == 0){ return Integer.MIN_VALUE; } max = A[0]; // 交换两个数的值 exchange(A,0,length); // 重新维护堆的结构 maxHeap(A,0,length); return max; } increaseKey(S,x,k) ： 将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字的值。 public void increaseKey(int[] A,int i,int key){ if(key < A[i-1]){ System.out.println("new key is smaller than key"); } A[i-1] = key; while(i > 0 && A[i-1] > A[i>>1]){ exchange(A,i-1,i/2); i = i>>1; } }