二叉堆与堆排序详解

"堆排序是一种基于完全二叉树结构的高效排序算法，它利用了堆的特性进行排序。堆可以是大顶堆或小顶堆，其中大顶堆的每个节点都大于或等于其子节点，小顶堆则相反。在完全二叉树中，从根节点到叶子节点的路径上的所有节点都按照堆的规则排列。堆排序的时间复杂度为O(n log n)，优于冒泡排序的O(n^2)。 堆排序的过程主要包括两个主要步骤：构建堆和堆调整。 1. 构建堆：首先，将待排序的序列构建成一个大顶堆（或小顶堆）。这可以通过从最后一个非叶子节点（即最后一个节点的父节点）开始，依次对每个节点执行下沉操作（sink）来实现。下沉操作通过比较节点与其子节点并根据需要交换位置来确保堆的性质得以保持。 2. 堆调整：堆顶元素（即当前最大或最小元素）与末尾元素交换，然后将末尾元素移除，堆的大小减一。接着对剩余元素重新调整为堆，重复此过程直到所有元素都被排序。 例如，以下是一个大顶堆的构建和调整过程： - 初始化：假设有一个数组[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]，首先将其视作一个完全二叉树，根据大顶堆规则，9是根节点，大于其子节点7和5。 - 构建堆：从倒数第二个非叶子节点（即5）开始，执行下沉操作。5与它的左子节点2比较，无需交换；接着5与右子节点6比较，也无需交换，因此堆的构造完成。 - 排序：9与10交换，数组变为[10, 7, 5, 11, 12, 2, 14, 3, 9, 6]，然后将10移除，剩下[7, 5, 11, 12, 2, 14, 3, 9, 6]，再次调整为堆，得到新的大顶堆[9, 5, 11, 12, 2, 14, 3, 7, 6]。 - 重复：9与6交换，数组变为[6, 5, 11, 12, 2, 14, 3, 7, 9]，9移除后调整为堆，得到[7, 5, 11, 12, 2, 14, 3, 6]，继续此过程直到所有元素排序完成。 在实际编程实现中，通常使用一维数组存储堆，因为完全二叉树可以用线性数组表示，父节点的索引i对应于子节点的索引2i和2i+1。例如，堆的插入（pushheap）过程如下： - 新元素添加到数组末尾，增加数组长度。 - 遍历从新元素开始到根节点的路径，如果新元素大于其父节点，则交换它们的位置。这个过程称为向上更新（sinkup），它确保了新的元素正确地嵌入到堆中。 堆排序由于其优秀的平均时间复杂度，常被用于需要快速排序大量数据的场景。同时，由于其原地排序和稳定性的特点，堆排序在内存有限或稳定性要求较高的情况下也是一种实用的选择。"