n(logn)级别排序三 堆排序

堆

在数据结构当中，对于先进先出的数据结构被称为队列，优先队列则是按照其优先级进行出队的操作。从队列的定义中可以看出，可以用一个数组来维护一个队列，其实现方式和出入队复杂度如下表所示

类型 入队 出队
普通数组 O(1) O(n)
顺序数组 O(n) O(1)
堆 O(lgn) O(lgn)

可以看出，数组的两种方式各有优缺点，堆虽然入队出队都没有最快，但是整体上是比较优秀的。另外，堆可以动态的进行优先级的维护操作，因此下面就学习堆这种结构。

堆的结构和实现

堆的结构

堆的结构是树形的，其一种经典实现是二叉堆，对应的树形结构便是二叉树。这个堆满足以下几个特点：

  • 所有的子节点都不大于其父节点
  • 它是一颗完全二叉树（除最后一层外，每一层的节点个数必须是最大值；最后一层的节点必须集中在左侧）

满足上面的性质就构成了一个堆，这样的堆被称为最大堆，因为由上面的定义可以看出，在顶层的节点总是这个堆中最大的，同理最小堆则反过来。

堆的实现

树的结构一般使用链表的形式，比如二叉树，对于每个节点，我们会定义左右两个指针，分别指向它的左孩子和右孩子。但对于完全二叉树来说它满足这样一个性质：

如果对一个完全二叉树自顶向下，从左到右编号的话，每一个左节点的序号都是其父节点的两倍，右节点则是父节点两倍加一（索引从1开始）

因此我们可以根据这个规律用数组来存储一个堆。下面的代码演示了在C++中定义一个最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//最大堆
class MaxHeap{
private:
    int* data;
    int count;

public:
    MaxHeap(int capacity){
        data = new int[capacity + 1];
        count = 0;
    }

    ~MaxHeap(){
        delete data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }
};

堆的插入操作

上面定义了一个堆的基本结构，根据二叉堆的定义，需要在插入一个新的元素的时候维护它的正确位置。插入的思想是这样的：在堆的后面插入这个叶子结点，判断它与其父节点的大小，如果大于父节点，则与父节点进行交换，直到满足不大于其父节点为止。这样就让新插入元素的堆依旧满足上述条件的要求。下面的代码定义了它的插入操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insert(int item){
        //从1位置开始放入的元素，此处要注意数组放满的情况
        data[count + 1] = item;
        count ++;
        //维护元素位置
        shiftUp(count);
    }

//重点在于`shiftUp()`方法：
 void shiftUp(int k){
        while(k > 1 && data[k/2] < data[k]){
            swap(data[k/2], data[k]);
            k /= 2;
        }
    }

shiftUp维护了元素的位置，在插入的过程中不断调整元素，使整个堆满足二叉堆的性质。

堆的取出操作

在插入元素时，不断的在维护新的结构，同样，在取出一个元素后，需要重新维护堆的元素位置以满足其性质。堆取出一个元素的操作过程如下：

取出根节点的值，将最后一个节点交换到根结点位置，然后判断该节点与其左右子节点的大小，不断循环往复，将该节点往下移动到其合适的位置，完成整个取出元素的操作。由上面对最大堆的定义可知，最后一个元素移动到根节点，它一定至少比其左右节点之一小，因此需要向下移动。

整个操作代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 //取出最大值，即跟节点
    int extractMax(){
        //堆中要有元素
        assert(count>0);
        int item = data[1];

        swap(data[count], data[1]);
        count --;
        shiftDown(1);
        return item;
    }

//主要方法
void shiftDown(int k){
        //如果有子节点
        while ( 2 * k <= count){
            //设j为将要和k交换的位置
            int j = 2 * k;
            //如果有右孩子，先比较右孩子
            if( j + 1 <= count && data[j+1]>data[j]){
                //如果右孩子比左孩子大，则交换位置变为右孩子
                j = j+1;
            }

            if(data[k] >= data[j]){
                break;
            }

            swap(data[k], data[j]);
            k = j;
        }
    }

重点在shiftDown方法上，while循环中的条件为判断其是否还有孩子节点，由于满足一颗完全二叉树可知，有孩子节点至少有左孩子, 左孩子节点下标为父节点两倍，所以乘以2。定义下标j为将要和k交换的初始位置，在看是否有右孩子，如果有看是否比左孩子大，如果比左孩子大，那这次交换就要和右孩子进行。找出左右孩子中最大的之后，在看它是否比父节点大，如果是就进行交换，并继续往下考察，否则结束。

对于上述面的shiftUp,shiftDown两个操作，与之前对希尔排序的一个优化类似，可以不用每次判断都进行交换操作，而是用赋值来代替。以shiftDown为例，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void shiftDown(int k){
     //记录K处的值
     int ok = data[k];
     //如果有子节点
     while ( 2 * k <= count){
         //设j为将要和k交换的位置
         int j = 2 * k;
         //如果有右孩子，先比较右孩子
         if( j + 1 <= count && data[j+1]>data[j]){
             //如果右孩子比左孩子大，则交换位置变为右孩子
             j = j+1;
         }

         if(ok >= data[j]){
             break;
         }

         //swap(data[k], data[j]);
         data[k] = data[j];
         k = j;
     }
     data[k] = ok;
 }

堆排序

从上面的方法中已经可以看出来，堆提供了一个每次取出最大值的方法，下面根据这个方法来进行排序

基础版

此处思路比较简单，只需要将排序的数组构造为一个最大堆，再依次取出最大值就好了。

1
2
3
4
5
6
7
8
9
10
void heapSort1(int arr[], int n){
    MaxHeap maxHeap = MaxHeap(n);
    for(int i=0;i<n;i++){
        maxHeap.insert(arr[i]);
    }

    for(int i=n-1;i>=0;i--){
        arr[i] = maxHeap.extractMax();
    }
}

建堆过程优化

第一种方式建立在堆的插入方法上，在给定一个数组的情况下，可以用另一种方式初始化一个最大堆，它的过程是这样的：首先将给定的数组构建一棵完全二叉树，此时该二叉树的所有叶子节点可以看作是一颗只有一个元素的最大堆，然后从第一个非叶子节点开始，对其进行shiftDown操作，直到整棵树满足最大堆的性质。在完全二叉树中，第一个非叶子节点的位置为节点数除以二，这样就可以确定它的位置。

代码演示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 //堆构造方法2
    MaxHeap(int arr[], int capacity){
        data = new int[capacity + 1];
        for(int i=0;i<capacity;i++){
            data[i+1] = arr[i];
        }
        count = capacity;
        //对非叶子进行shiftDown操作
        for(int i = capacity/2; i >= 1; i--){
            shiftDown(i);
        }

    }

//构造堆方式优化
void heapSort2(int arr[], int n){
    MaxHeap maxHeap = MaxHeap(arr, n);
    for(int i=n-1;i>=0;i--){
        arr[i] = maxHeap.extractMax();
    }
}

该方式较快的原因是下面的结论：

将n个元素依次插入堆中的算法复杂度为O(nlogn),而第二种方式的算法复杂度为O(n)

原地堆排序

上面的排序都基于堆的性质，开辟了一个新的空间来完成排序的过程。从堆的shiftDown操作来看，它是在一个数组中完成的，因此，可以这样操作：先把给定的数组构建为一个最大堆，每次取出最大值放到后面，再把前面部分构建为最大堆。这样就可以对一个数组完成排序了。下面用代码演示一下这个过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//在arr中对其前n个元素中的第k个进行shiftDown操作
void __shiftDown(int arr[], int k, int n){
    while (2* k+1 < n){
        int j = 2 * k +1;
        if(j+1<n && arr[j]<arr[j+1]){
            j = j+1;
        }
        if(arr[k]>arr[j]){
            break;
        }
        swap(arr[j], arr[k]);
        k = j;
    }
}

//原地堆排序
void heapSort(int arr[], int n){

    //将数组构建成一个最大堆
    for(int i=(n-1)/2;i>=0;i--){
        __shiftDown(arr, i, n);
    }

    // 每次取出最大值，再进行shiftDown操作
    for(int i= n-1; i>0; i--){
        swap(arr[i], arr[0]);
        __shiftDown(arr, 0, i);
    }

}

可以看到，理解了最大堆的思想后，脱离最大堆来完成这个排序也是很简单的。此处直接对数组进行排序，下标从1开始，所以几个节点的位置发生了变化：左节点 = 父节点*2+1，右节点 = 父节点*2+2，第一个非叶子节点 = (节点数-1)/2,在使用的时候需要注意。