图解堆排序算法

2021/4/29 12:27:40

本文主要是介绍图解堆排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

关注下方公众号,分享硬核知识

01

演进

结点和边,构成一个图。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

不含环的连通图,便成了一棵。每个结点拥有的子结点数称为结点的

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

多棵树便构成了一个森林

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

结点的度最大为2的树便是二叉树;最大度为N的是N叉树,或多叉树

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

除叶子结点,每个结点的度都为2,称为满二叉树
除去最后一层之后的子树为满二叉树,且最后一层结点依次从左到右分布,则称为完全二叉树

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

如果在完全二叉树上再加一个限制条件:如结点都大于等于其子结点,或者小于等于其子结点,则称为
每个结点都大于等于其子结点,称为大根堆
每个结点都小于等于其子结点,称为小根堆

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

02

堆存储

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

2.1

顺序存储:数组

用数组存储,将一个线性数组映射成一棵完全二叉树,父结点为i,则左儿子为2i+1,右儿子为2i+2。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码如下

int heap[10];

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

2.2

链式存储:链表

定义一个结点的结构体,两个指针分别指向左儿子和右儿子。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码如下

struct Node {
    int value;
    Node *lson, *rson;
};
Node *heap;

以下思想都以大根堆举例

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

03

堆调整

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

3.1

向上调整

子结点与父结点的下标关系如下:

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

用一个指针指向待调整的结点:

  • 先比较是否大于父结点,如果大于就进行交换,并将指针上移到父结点

直到指向根结点或者当前结点小于等于父结点。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码实现

//将heap[k]向上调整
int heapUp(int *heap, int k) {
    int parent, son, x;
    x = heap[k];
    son = k;
    parent = (son - 1) / 2;
    while (son > 0) {
        //如果父结点大于等于heap[k]则退出,否则将父结点下移
        if (heap[parent] >= x)
            break;
        heap[son] = heap[parent];
        son = parent;
        parent = (son - 1) / 2;
    }
    heap[son] = x;
    return 0;
}

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

3.2

向下调整

父结点与子结点的下标关系如下:

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

用一个指针指向待调整的结点:  

  • 先比较两个子结点哪个更大,取出更大的子结点

  • 再比较更大的子结点是否大于父结点,如果大于就进行交换,并将指针下移

直到指向叶子结点或者当前结点大于两个子结点。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码实现

//将heap[k]向下调整
int heapDown(int *heap, int k, int n) {
    int parent, son, x;
    x = heap[k];
    parent = k;
    son = 2 * k + 1;    //左孩子结点
    while (son <= n) {
        //比较左右儿子,选择较大的一个
        if (son + 1 <= n && heap[son + 1] > heap[son])
            son++;    //使son指向左右孩子中较大的结点。
        //如果儿子结点中较大的都小于等于待调整结点则退出,否则将子结点上移
        if (heap[son] <= x)
            break;
        heap[parent] = heap[son];
        parent = son;
        son = 2 * parent + 1;
    }
    heap[parent] = x;
    return 0;
}

04

增减元素

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

4.1

PUSH

从堆尾插入元素,再对该元素进行向上调整直到满足堆性质。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

4.2

POP

将堆顶弹出,用堆尾的元素置换,再对堆顶的元素进行向下调整。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

05

构建堆

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

5.1

插入构建

依次向堆尾插入元素,并对该元素进行向上调整,直到满足堆性质。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

时间复杂度:
插入一个元素要调整的高度为logi,所以插入n个元素的总次数为log1+log2+...+logn=log(n!)。

根据斯特林公式,有如下证明,所以复杂度O(nlogn)。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

5.2

调整构建

待调整的数组,可以直接看成是一棵完全二叉树。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

从(n-1)/2位置开始,将每个元素进行向下调整,直到根结点。对于每一个待调整的当前结点,下面的子树都已经满足堆性质,所以调整完所有结点便成了堆。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

时间复杂度:
倒数第二层有2^(h-2)个结点,调整高度为1,依次类推,第一层有1个结点,调整高度为h-1,整体加起来的复杂度为O(n)。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码实现

void buildHeap(int *heap, int n) {
    for (int i = (n - 1) / 2; i >= 0; --i) {
        heapDown(heap, i, n);
    }
}

06

排序

一个已经调整完成的大根堆。

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

核心思想:  

  • 将堆顶与堆尾的元素置换

  • 整体元素长度减1

  • 对堆顶元素进行向下调整

重复以上过程直到整体元素为1,这时就变成了一个升序排列的数组。  

模拟过程:

Step 1

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

Step 2

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

代码实现

void swap(int *heap, int a, int b) {
    int temp;
    temp = heap[a];
    heap[a] = heap[b];
    heap[b] = temp;
}
void heapsort(int *heap, int n) {
    for (int i = n; i > 0; --i) {
        swap(heap, 0, i);
        heapDown(heap, 0, i - 1);
    }
}

07

总结

堆排的复杂度为nlogn,应用场景很广泛,这篇文章主要讲清楚堆相关的操作,具体的应用和建模以后会再专门写文章讲解。

如果喜欢小K的文章,请点个关注,分享给更多的人,小K将持续更新,谢谢啦!

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

关注下方公众号,分享硬核知识

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

关注我,涨知识

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

原创不易,感谢分享

转发,点赞,在看

往期精彩回顾

一道错误答案传遍全网的逻辑面试题

腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?

一道充满歧义的思维题,全网唯一刁钻分析

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

分享给更多朋友,转发,点赞,在看



这篇关于图解堆排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程