[数据结构与算法]堆排序理解

• 堆排序第一步 这一步不需要程序 只是一个概念上的理解

实际上是从上往下，从左往右将vector? a[ ]中的数值，放成一棵完全二叉树；

若父节点为a[i]，则左右子节点分别为a[2i+1]和?a[2i+1]。

若子节点为a[i]，则父节点为a[(i-1)/2]。

• 堆排序第二步? 建堆

从最后一个节点处，开始做交换；

求出最后一个节点a[i]的父节点a[(i-1)/2]，再判断父节点和两个子节点的大小，找出最大值。

如若节点之间发生交换，则递归进行交换节点处的最大值的判断(这里的判断是向下进行的)。直到递归结束（结束的条件是到达叶子节点或者没有进行交换），在进行上一个节点a[i-1]的判断,直到a[0]。

• 堆排序 第三步

从最后一个节点处开始与第一个节点交换位置，进行堆排序第二步。

之后将最后一个节点摘除，重复进行节点交换以及堆排序的第二步，知道所有节点被摘除。

摘除的顺序是从大到小的顺序，即为堆排序的最后结果。

• 参考文献：

堆排序(heapsort)_哔哩哔哩_bilibili? ?这个视频讲解很细致，以上是根据这个视频的个人理解。