堆排序

来自计算思维百科
跳转至: 导航搜索
堆排序.png

如果我们希望对很多数据按照从小到大或是从大到小的顺序重新放置,这就是排序。堆排序是一种利用堆的特性对数据进行排序的方法。

基本概念

首先先介绍一下什么是堆。堆是一个二叉树,就是每个节点有左子节点有右子节点,我们以最大堆为例,所谓最大堆是要满足:任何时候,父节点都比两个子节点大。在堆中,只有最后一个父节点(最优下角的父节点)可能有一个子节点,其他父节都要有两个子节点。

堆排序利用了二叉树的树形结构进行排序。按照完全二叉树的编号次序,将数据存放在相应的结点,这个时候是不满足堆的条件的。下面,就要对堆进行调整。然后从叶子结点开始,从互为兄弟的两个结点中(没有兄弟结点除外),选择一个较大(或较小)者与其双亲结点比较,如果该结点大于(或小于)双亲结点,则将两者进行交换,使较大(或较小)者成为双亲结点。将所有的结点都做类似操作,直到根结点为止。这时,根结点的元素值的关键字最大(或最小)

堆排序的优点是每次从堆顶部拿到的数据都是最大或是最小的,然后再对堆进行调整,就可以取下一个大的或是小的数。

应用范围

任何需要排序的地方都可以应用堆排序。

使用方法及步骤

  1. 利用数据构建堆;
  2. 从堆的根拿到最大或最小的数;
  3. 对堆进行调整;
  4. 重复2,3步骤。

应用案例

应用1- 包裹投递

案例:双十一到了,快递公司的快递比平常多了好几倍,投递的压力就大了,按照包裹的紧急度进行堆排序,位于根结点处的包裹优先处理,再经过一轮堆排序,马上可以找到次优处理的包裹,这样可以大大的提高投递时间效率,提高快递公司的工作效率。

应用2-医院挂号

案例:堆排序也可以用在医院挂号处理,病人都有自己的编号,医生按编号进行诊断,可是每个病人的病情紧急程度不同,这时候,如果综合每个病人的病情,用堆排序的方法进行排序,让病情严重的病人先就诊,剩下的病人再调整为一个堆,下一次就是次严重的病人就诊。这种人性化的管理,也节省了时间。

可以体现的计算思维

堆排序利用堆这种数据结构实现了数据之间的大小比较,体现了计算思维的抽象特点。