【排序算法】堆排序的推导及实现

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
-- 维基百科

数据结构

堆是用来表示元素集合的一种数据结构。在其他一些场合中，“堆”是指能够分配可变大小的结点的一段较大的内存。示例中堆用于表示数值，但实际上堆中的元素可以是任何数据类型。
下图给出了一个8元的堆以及用8元数组表示的隐式树实现：


由于形状性质是通过表示方法来保证的，我们约定“堆”这个词意味着任何节点的值都大于或等于其夫结点的值。更准确的说:
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

【排序算法】堆排序的推导及实现

原文：https://www.cnblogs.com/charles101/p/14055491.html