① 【跟着小蛋刷算法】什么是堆如何实现堆排序，满满的干货来了
堆可以理解为特殊树形结构，满足两个条件：完全二叉树与值的比较规则（大顶堆或小顶堆）。完全二叉树特点是除最后一层外，其他层节点满载，最后一层靠左排列。大顶堆为每个节点大于或等于子节点，小顶堆为每个节点小于或等于子节点。以下图示为堆的示例。
构建堆采用数组形式。每个节点存储在数组的第二位置开始，定义节点在数组的位置为i，左子节点为2i，右子节点为2i+1。通过此规律可以推导出节点关系。接下来通过代码实现堆的各种功能。
往堆中插入元素时，需满足堆的特性。如果插入后不满足，执行堆化操作，即新插入的节点与父节点比较，若不满足子节点小于等于父节点则交换节点值，重复过程直到堆满足特性。此过程如图示。
删除堆顶元素，即删除堆中最大元素。将堆顶元素值与最后一个节点值互换，再执行堆化过程，直到堆满足特性。图示此过程。
堆排序利用堆进行排序。首先将序列构造成大顶堆，最大值在堆顶。接着交换堆顶元素与末尾元素，将剩余元素重新构造成堆，得到次大值，反复执行得到有序序列。
实现堆排序的第一步是构建大顶堆，采用从上往下的堆化方式。假设待排序序列{0,7,5,19,8,4,1,20,13,16}，堆元素从数组下标1开始，总共有9个元素。循环从9/2=4开始，直至1，因为这些节点有子节点。
排序过程是不断将堆顶元素与末尾元素交换，将堆元素减1，然后重新堆化，重复直至完成排序。整个过程如图所示。
堆排序时间复杂度包括构建堆与排序，构建堆为O(n)，排序为O(nlogn)，整体时间复杂度为O(nlogn)。
堆的概念、插入与删除操作、堆排序与排序代码详解。总结堆知识点，堆排序流程，以及建堆和排序的代码实现。
堆的知识点已大致讲解，但算法之路漫长，继续坚持学习。关注小蛋，一起交流进步，更多的算法干货将不断推出。