平均情况、最好情况和最坏情况的时间复杂度都为O(nlog2n)，即线性对数复杂度，不稳定的排序算法。
堆结构在 数据结构：二叉完全树（堆） 一文中进行了分析，接下来用代码来实现其几个关键操作：弹出、插入、取顶、上浮、下沉
堆操作实现
这里的实现以小根堆为例：
image.png
堆的基本操作接口定义：
image.png
弹出方法
弹出时将数组尾元素放到到数组首部，然后对数据首部（根节点）执行下沉操作即可。
image.png
插入方法
插入时将新元素放到数组尾部，然后对尾部元素执行上浮操作即可。
image.png
取顶方法
返回数组首部元素即可
image.png
上浮方法
image.png
下沉方法
image.png
数组元素交换方法以及获得所有元素方法
image.png
堆排序的实现
创建新的数组，将所有待排序元素 push 到二叉堆结构中，然后依次弹掉堆顶即可。堆结构在每次执行pop方法时都会执行下沉操作使堆结构中保存的数组的第一个元素为排序后下一个位置应该存放的元素。
实现类为 HeapSort
image.png
测试
测试
代码已上传 GitHub，可以在 这里 找到
网友评论