HeapSort 堆排序

0. 前言

本文继续分析另一个很重要的高效排序算法——堆排序。不过，在此之前，需要先引入堆和优先队列的概念，这是堆排序的基础。

1.优先队列（Priority Queue）

基本概念

顾名思义，优先队列是由队列演变而来的，包含最基本的插入和删除操作。优先队列的插入规则与队列一致，是插入（添加）到队列的末尾；删除规则比较特殊，是删除（在指定规则中）优先级最高的项。

（最大项）优先队列API如下：

public class MaxPQ<Key extends Comparable<Key>>{
    MaxPQ() //构造函数
    MaxPQ(Key[] a) //构造函数
    void insert(Key v) //插入项、添加项
    Key delMax() //删除最大值
    boolean isEmpty() //判空
    Key max() //查找最大值
    int size() //查询长度
}

简单应用

想象一个场景：从总数为N的列表中个找出最大的M个项。
方法一：将N列表排序（使用快速排序或者归并排序，从大到小排），然后选择前M项即可。
方法二：使用优先队列，当队列大小达到M时，开始将最小值出队。

方法二的代码如下：

//MinPQ是alg4提供的最小优先队列API
MinPQ<Transaction> pq = new MinPQ<Transaction>();

while (StdIn.hasNextLine()){
    String line = StdIn.readLine();
    Transaction item = new Transaction(line);
    pq.insert(item);
    //当队列长度达到M时，每读取一个数字入队后，就将最小值删除
    if (pq.size() > M)
        pq.delMin();
}

方法一与方法二的对比

实现方法

优先队列可以使用有序数组或者无序数组来实现。使用有序数组时，每次插入都要与数组中原来的项比较，然后插入适当的位置；每次删除只需删除数组最后一项。使用无序数组时，每次插入时插入到数组的最后一项；每次删除时要查找出数组中优先度最高的项，然后与最后一项交换，删除最后一项。

以下是无序数组的实现方式

public class UnorderedMaxPQ<Key extends Comparable<Key>>{

    private Key[] pq; // 定义无序数组
    private int N; // 定义数组长度
    public UnorderedMaxPQ(int capacity){
        pq = (Key[]) new Comparable[capacity];
    }

    public boolean isEmpty(){ return N == 0; }
    //插入到数组最后一项
    public void insert(Key x){ pq[N++] = x; }
    //删除优先度最大的项
    public Key delMax(){
        int max = 0;
        for (int i = 1; i < N; i++)
            if (less(max, i))
                //查找到最大项
                max = i;
        //与最后一项交换
        exch(max, N-1);
        return pq[--N];
    }
}

优先队列是有序数组和无序数组的实现方法的性能比较

2.二叉堆

上一小节的最后一张图表明使用有序数组或者无序数组来实现优先队列均不是最优的方案，因此本节介绍二叉堆这个结构来实现优先队列，可以将各项操作的时间性能降低到lgN。

基本概念

先上概念，二叉堆本质上就是一种堆有序的完全二叉树。
所谓的完全二叉树就是除了最低层外完全平衡的二叉树，如下图所示

完全二叉树具备以下性质：

• N个节点的完全二叉树的高度是lgN
• 只有节点数量达到2的数量级时才增加树高

所谓的堆有序的二叉树是指每个节点均代表一个值，父节点的值不小于其子节点的值，下图就是一个堆有序的二叉树

二叉堆最简单的表示形式就是使用数组表示：从第1位开始，下标的关系标志树层的关系，无需指针练连接。

如何使用下标表示树层呢？

• 节点K的父节点一定是k/2

• 节点k的子节点分别是2k 和2k+1

• 注意一定要从下标1开始记录（不能从下标0开始）

下标表示树层的示意图

基本操作

使用二叉堆实现优先队列，最基本的操作包括：插入和删除。
根据二叉堆的特性（数组表示法）不难发现，随机插入一个项、删除优先项都很有可能打乱二叉堆。

场景一

问题：子节点的值大于父节点
解决方法：交换子节点与父节点的位置，直到堆有序
示意图：

代码实现

//将节点K浮上去
private void swim(int k){
    while (k > 1 && less(k/2, k)){
        //如果k/2（父）小于k（子），交换位置
        exch(k, k/2);
        k = k/2;
    }
}

时间性能：至多lgN+1次比较操作（树高）

因此，插入时就是将值插入数组最后一项，然后调用swim()将其上浮到合适位置，保证堆有序。

public void insert(Key x){
    pq[++N] = x;
    swim(N);
}

场景二

问题：父节点的值小于其子节点（一个或者两个）
解决方法：交换父节点与较大的子节点，直到堆有序
示意图：

代码实现

//将节点K沉上去
private void sink(int k){
    while (2*k <= N){
        int j = 2*k;
        if (j < N && less(j, j+1))
            //选择值较大的子节点
            j++;
        if (!less(k, j)) break;
        //如果k（父）小于j（子），交换位置
        exch(k, j);
        k = j;
    }
}

时间性能：至多需要2lgN次比较。

因此，删除的时候就是交换root（下标1）与数组最后一项，删除最后一项后，对root调用sink()，将其下沉到适合的位置，保证堆有序。

public Key delMax(){
    Key max = pq[1];
    exch(1, N--);
    sink(1);
    pq[N+1] = null;
    return max;
}

代码实现

//定义了MaxPQ这个最大项优先队列
public class MaxPQ<Key extends Comparable<Key>>{
    private Key[] pq;
    private int N;

    public MaxPQ(int capacity)
    { pq = (Key[]) new Comparable[capacity+1]; }
    //判空
    public boolean isEmpty()
    { return N == 0; }
    //插入
    public void insert(Key x){
        pq[++N] = x;
        swim(N);
    }
    //删除
    public Key delMax(){
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max; 
    }
    //上浮
    private void swim(int k){
        while (k > 1 && less(k/2, k)){
            //如果k/2（父）小于k（子），交换位置
            exch(k, k/2);
            k = k/2;
        }
    }
    //下沉
    private void sink(int k){
        while (2*k <= N){
        int j = 2*k;
        if (j < N && less(j, j+1))
            //选择值较大的子节点
            j++;
        if (!less(k, j)) break;
        //如果k（父）小于j（子），交换位置
        exch(k, j);
        k = j;
        }
    }
    //辅助函数：比较和交换
    private boolean less(int i, int j){
        return pq[i].compareTo(pq[j]) < 0;
    }
    private void exch(int i, int j){
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

有序数组、无序数组和二叉堆的实现方法的性能比较

另外，需要考虑一种情况——二叉堆的大小超过了数组的长度，此时就要使用可调整大小的数组（resizing array）

3.堆排序

原理

讲完以上概念之后，下面正式分析堆排序算法。堆排序就是先将无序序列构造成二叉堆，然后逐此将root节点与无序序列中的最后一个值交换，重复直到序列有序。
这里使用了两次循环，第一次循环是自底向上检查，构造二叉堆；第二次循环是重复交换root与无序序列中最后一个节点，遍历完所有节点。

第二次循环的示意图

• 1.E 与X (ROOT)交换，同时E 下沉到其适合位置。此时X 有序，其他无序；

• 2.E 与T (ROOT)交换，同时E 下沉到期适合位置。此时X T 有序，其他无序；

• 3.以此类推。

代码实现

public class Heap{
    public static void sort(Comparable[] a){
        int N = a.length;
        //第一次循环
        for (int k = N/2; k >= 1; k--)
            sink(a, k, N);
        //第二次循环
        while (N > 1){
            exch(a, 1, N);
            sink(a, 1, --N);
        }
    }
    private static void sink(Comparable[] a, int k, int N)
    { /* as before */ }
    private static boolean less(Comparable[] a, int i, int j)
    { /* as before */ }
    private static void exch(Comparable[] a, int i, int j)
    { /* as before */ }
}

对比

作为高效的排序算法，快速排序、归并排序、堆排序对比如下：

空间使用率

• 归并排序：线性级的额外空间N

• 快速排序：常数级额外空间in place

• 堆排序：常数级的二外空间in place

时间性能

对排序最多使用了2NlgN次比较和交换

4.第4周作业答案

8puzzle