堆排序

堆定义

n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质):

(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤ n/2)，当然，这是小根堆，大根堆则换成>=号(2)ki>=k(2i)且ki>=k(2i+1)(1≤i≤ n/2)。k(i)相当于二叉树的非叶子结点，K(2i)则是左子节点，k(2i+1)是右子节点

若将此序列所存储的向量R[1..n]看做是一棵**完全二叉树**的存储结构，则堆实质上是满足如下性质的完全二叉树:img

树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

高度

堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O(lgn)。

动图演示

堆排序

代码实现

思路：

  1. 构造一个大根堆.
  2. 挨个取数.

构造大根堆 ：

定义函数sift：把一个除了第一个位置以外的其他子书均为大根堆的二叉树调整为大根堆.

那么从最后一个含有子节的节点到第一个节点依次执行sift函数即可构造成大根堆.

挨个取数：

把建成的堆第一个数和最后一个数交换位置然后执行sift函数.

见代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <stdlib.h>

void sift (int a[],int high,int low);
// 向下调整函数，把一个堆转换成一个大根堆

void heap_sort (int a[],int high,int low);

int main(){
    int a[]={45,99,55,1,5,6,8,3,46,24,15,36,11};
    int high=sizeof(a)/sizeof(a[0]);
    heap_sort(a,high-1,0);
    for(int i = 0;i<high;i++){
        printf("%d ",a[i]);
    }
    system("pause");
    return 0;
}

void sift (int a[],int high,int low){
    int temp = a[low];
    int i = low;
    int j = 2*i+1;
    while (j<=high){
        if (j<high && a[j+1]>a[j]) {
              //j<high 保证j+1下标存在
        j = j+1;
        
        }
        if (a[j]>temp){
            a[i] = a[j];
            i = j;
            j = 2*i+1;
        }
        else{
            break; 
        }
    }
    a[i] = temp;
    // 直到堆顶的数找到自己的位置
}

void heap_sort (int a[],int high,int low){
    // 建一个堆
    for (int i=(high-1)/2;i>=0;i--){  //从每个父子节到最顶
        sift(a,high,i); 
        /*
        这个high准确来说应当是每个堆的的最后一个值，但在某些子堆的最后
        一个值下标，较难求出，也可用整个堆的high来表示
        */
    // 从最后开始取数。
    }
    for (int k = high;k>=0;k--){
        int tep = a[k];
        a[k] = a[low];
        a[low] = tep;
        sift(a,k-1,0);
    
    }

}

输出结果

1 3 5 6 8 11 15 24 36 45 46 55 99

分析

时间复杂度很容易得出为O（nlogn）.

基于堆排序的topk问题

要输出一个数组中的前k大的数（k<=n，n为数组长度），直接使用堆排序然后遍历那么他的时间复杂度为O（nlogn），若使用冒泡、选择、插入，时间复杂度为O（kn），如果n较大，k较小时，后者的复杂度相对较低一些。那么则可以通过构造一个k大小的小根堆，然后遍历数组，在逆序输出.

topk代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>

// 首先构造一个小根堆

void sift (int *a,int low,int high);

int topk (int *a,int low ,int high,int k,int heap[]);

int main (){

    int a[] = {88,94,55,6,42,30,4,15,85,36,11,31};
    int high = sizeof(a)/sizeof(a[0]);
    int k = 3;
    int heap[k-1];
    topk(a,0,high-1,k,heap);
    for (int i = 0;i<k;i++){
        printf("%d ",heap[i]);
    }

    system("pause");
    return 0;
}


// 向下调整函数 ，调整为小根堆

void  sift (int *a,int low,int high){
    int temp = a[low];
    int i = low;
    int j = 2*i+1;
    while (j<=high){
        if (j<high && a[j+1]<a[j]){
            j = j+1;
        }
        if (a[j]<temp){
            a[i] = a[j];
            i = j;
            j = 2*i+1;
        }
        else{
            break;
        }
    }
    a[i] = temp ;
}  // 与大根堆sift函数类似，只是两处判断语句的地方换成了小于

int topk (int *a,int low ,int high ,int k,int heap[]){
    // 建堆（k大小）
    
    for (int i =(k-2)/2;i>=0;i-- ){
        sift(a,i,k-1);
    }
    
    for (int i = 0;i<k;i++){
        heap[i]= a[i];
    }
    // 遍历数组，把符合要求的数放入到k大小的小根堆中
    for (int i =k ;i<=high;i++){
        if (a[i]>a[low]){
            a[low] = a[i];
            // a[low] 是k大小堆中最小的数
            sift(heap,0,k-1);
        }
    }
    // 出数
    for (int i = k-1;i>=0;i--){
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp ;
        sift (heap,0,i-1);
    }
    return heap[k-1];

}

输出结果

94 88 55

时间复杂度

可以看出是O（nlogk），相对向前两者更高效.