基于二叉堆实现的优先队列和堆排序_基于二叉堆的优先队列

堆的定义

在二叉堆数组中，每个元素都要保证大于等于另外两个特定位置的元素。

堆有序：当一颗二叉树的节点都大于等于它的两个子节点的时候，被称为堆有序，根节点是堆有序
二叉树的最大节点。

• 二叉堆的定义
  

  二叉堆是一组能够用堆有序的完全二叉树排序的元素，并且在数组中按照层级存储（不使用数组的第一个位置）
  不使用数组第一个位置，即数组是开始从1放置元素。在一个堆中，位置为k的结点的父节点的位置是[k/2],它的两个子节点的位置是2*k, 2*k+1。在不使用指针的情况下，可以计算数组的索引上下移动。
  一颗大小为N的完全二叉树的高度是[lgN].

堆的算法

• 由下至上的堆有序化(上浮)

  如果堆的有序状态因为某个节点比它的父节点更大而打破，那么我们就需要交换它和它的父节点来修复堆，交换后这个节点比它的两个字节点都大（一个是曾经的根节点，另一个比曾经的根节点更小）。但是这个节点可能比它的父节点更大，所以我们通过这个方法来恢复秩序。位置k的父节点是k/2.

• 代码实现

void swim(int k)
{
    while(k > 1 && less(k/2, k))  //k指向的是非根节点
    {
        exch(k, k/2);
        k = k/2;
    }
}
1
2
3
4
5
6
7
8

• 由上至下堆有序化(下沉)

  如果堆的某个节点因为变得比它的两个子节点或是其中之一更小而被打破了，那么就可以通过将它和它的两个子节点中的较大者交换来恢复堆。交换可能在子节点处继续打破堆的有序状态，因此我们不断通过这种方式将其修复，直到堆有序或者达到了最后一个节点N。

• 实现代码

void sink(int k)
{
    while(2*k <= N) //有左孩子的时候继续
    {
        int j = 2*k;//左孩子节点
        if(j < N && less(j, j+1)) j++; //有右孩子且右孩子教大，则j指向右孩子
        if(!less(k,j)) break;//如果根节点大于孩子节点，证明堆有序，停止。
        exch(k, j);//交换根节点和孩子节点’
        k = j;//k指向新的根节点
    }
}
1
2
3
4
5
6
7
8
9
10
11

• 插入元素

  将新元素加到数组末尾，增加堆的大小并且让这个新元素上浮到合适的位置

• 实现代码

//N的初始值没有使用，为0
public void insert(int v)
{
    pq[++N] = v;
    swim(N);//上浮
}
1
2
3
4
5
6

• 删除最大元素
  

  从数组顶端删除最大的元素并且将数组最后一个元素放到顶端，减少堆的大小并且让这个元素下沉到合适的位置

public int delMax()
{
    int max = pq[1];  //从根结点得到最大元素
    exch(1, N--);//N指向数组中的最后一个节点
    pq[N+1] = mull; //防止对象游离
    sink(1);   //恢复堆的有序性
    return max;
}
1
2
3
4
5
6
7
8

总结

优先队列是一个基于堆的表示，存储与数组pq[1..N]中，pq[0]没有使用，在insert()中，我们将N加一并且把新元素添加到数组最后，然后用swim()恢复堆的秩序。在delMax()中，我们从pq[1]中得到需要返回的元素，然后将pq[N]移动到pq[1],将N减少1并用sink()恢复堆的秩序。同时我们还将不使用的pq[N+1]设为null.让系统回收它的空间。

堆排序

堆排序可以分为两个阶段：将原始的数组重新组织安排进一个堆中，然后在下沉排序阶段取出元素。

• 堆的构造

  第一种方法：从左至右遍历数组，用swim()保证指针左侧所有元素都是一颗堆有序的完全树就可以，时间复杂度是NlgN
  第二种方法:从右到左通过sink()方法，数组中的每一个位置都是一个子堆的根节点了，如果一个节点的两个子节点都是堆了，那么在该节点上调用sink()方法可以将它们变成一个堆。

• 下沉排序

  将堆的最大值删除，然后放在堆减少后空出的位置

• 实现的代码

public void sort(int[] 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);//恢复堆的有序性
    }
}
1
2
3
4
5
6
7
8
9
10
11