数据结构与算法系列文章：数据结构与算法目录
堆排序，是利用堆这种数据结构，将排序数组看成是一棵完全二叉树的顺序存储结构，来进行排序的算法。
解释一下堆和二叉树：
堆：
堆(heap)又被为优先队列。尽管名为优先队列，但堆并不是队列。
因为队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。
而堆虽然在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。
堆的一个经典的实现是完全二叉树，这样实现的堆称为二叉堆。
满二叉树与完全二叉树：
满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树，如下图：
满二叉树.png
可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。
完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧，如下图：
完全二叉树.png
堆的特性：
1、必须是完全二叉树；
2、任一结点的值是其子树所有结点的最大值或最小值；
最大值时，称为“最大堆”，也称大顶堆；
最小值时，称为“最小堆”，也称小顶堆，如下图：
最大堆、最小堆.png
堆排序基本思想：
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。
堆与数组的关系：
堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ， 右节点在数组中的位置（数组下标）为 i * 2 + 2 。
实现：
/// <summary>
/// 堆排序算法
/// </summary>
/// <param name="arr"></param>
public void HeapSort(int[] arr)
{
// 构建大顶堆（初始状态看出：整体无序）
BuildMaxHeap(arr);
for (int i = arr.Length - 1; i > 0; i--)
{
// 将堆顶元素依次与无序区的最后一位交换（取出堆顶元素进入有序区）
Swap(arr, 0, i);
// 重新将无序区调整为大顶堆
MaxHeapify(arr, 0, i);
}
}
/// <summary>
/// 构建大顶堆（根节点大于左右节点）
/// </summary>
/// <param name="arr"></param>
private void BuildMaxHeap(int[] arr)
{
// 根据大顶堆的性质可知：数组的前半段的元素为根节点，其余都为叶节点
// 遍历调整：从最底层的最后一个根节点开始进行大顶堆调整
for (int i = arr.Length / 2; i >= 0; i--)
{
// 调整大顶堆
MaxHeapify(arr, i, arr.Length);
}
}
/// <summary>
/// 大顶堆调整过程
/// </summary>
/// <param name="arr">待调整的数组</param>
/// <param name="currentIndex">待调整元素在数组中的位置</param>
/// <param name="length">堆中所有元素个数</param>
private void MaxHeapify(int[] arr, int currentIndex, int length)
{
// 左子节点在数组中位置
int leftChild = 2 * currentIndex + 1;
// 右子节点在数组中位置
int rightChild = 2 * currentIndex + 2;
// 记录此根节点、左子节点、右子节点，三者中最大值的位置
int large = currentIndex;
// 与左子节点进行比较
if (leftChild < length && arr[leftChild] > arr[large])
{
large = leftChild;
}
// 与右子节点进行比较
if (rightChild < length && arr[rightChild] > arr[large])
{
large = rightChild;
}
if (currentIndex != large)
{
// large发生变化：左右节点中有大于跟节点的情况
// 将左右节点中的大者，与根节点进行交换，即：实现局部大顶堆
Swap(arr, currentIndex, large);
// 以上次调整动作的large位置（为此次调整的根节点位置），对整个进行递归调整
MaxHeapify(arr, large, length);
}
else
{
// large没有变化，不需要调整
}
}
/// <summary>
/// 交换数组的两个元素
/// </summary>
/// <param name="arr"></param>
/// <param name="i"></param>
/// <param name="j"></param>
private void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
网友评论