算法2.7

可以把任意优先队列当作一种排序方法:将所有元素插入一个查找最小元素的优先队列,重复调用删除最小元素,使用基于堆的优先队列实现此算法即堆排序

堆排序可以分为两个阶段:

  1. 堆的构造阶段:将原始数组重新组织安排进一个堆中

对于N个给定的元素,我们可以从左到右遍历数组,用swim()保证扫描指针左侧的所有元素是一棵堆有序的完全树.但更高效的办法是从右至左用sink()构造子堆,因为数组的每一个位置都是一个子堆的根节点,sink()对于这些子堆也适用.只需要扫描数组中一半元素,因为可以跳过大小为1的堆,即完全树最后一排.

  1. 下沉排序阶段:从堆中按递减顺序取出所有元素并得到排序结果

下沉排序中,将堆中最大元素删除,然后放入堆缩小后空出的位置.此处的”删除”只是暂时搁置的状态,不是真的删去.

  1. private static void sink(Comparable[] a, int k, int N){
  2.         while(2*k <= N){
  3.             int j = 2*k;
  4.             if(j < N && less(a,j,j+1)) j++;
  5.             if(!less(a, k, j)) break;
  6.             exch(a, k, j);
  7.             k = j;
  8.         }
  9.     }
  11. public static void sort(Comparable[] a){
  12.         int N = a.length - 1;
  13.         //从右至左sink构造子堆,且可以跳过大小为1的子堆
  14.         for(int k = N/2; k >= 1; k--) sink(a, k, N);
  15.         while (N > 1){
  16.             exch(a, 1, N--);//删除最大元素,放入堆缩小后空出位置
  17.             sink(a, 1, N);//恢复顺序
  18.         }
  19.     }

算法分析

将N个元素排序,堆排序只需少于(2NlgN+2N)次比较(以及一半次数的交换)

证明:2N来自于构造堆时,依次构造3,7,15,31…的堆,2NlgN来自于每次下沉最大可能要2lgN次比较

算法特点

堆排序是所知唯一能同时最优地利用空间和时间的方法,但现在系统很多应用很少使用,因为它无法利用缓存

Review

  1. 关于N=a.length-1,在MaxPQ中,pq[0]无元素,insert()中++N,N和最大角标始终相等,即最末尾为元素pq[i],那N==i,类比堆排序中,调用sort()的数组长length,但最末尾元素为a[lenght-1],N应该为a.length-1
  2. 边界取等问题:
  • sort()堆构造阶段for(int k = N/2; k >= 1; k--) sink(a, k, N),k>=1,当k=1时就是使得sink(a[1])
  • sort()下次排序阶段while (N > 1),若取1,最后exch(a,1,1)无意义