通过交互式可视化深入理解算法运行过程
堆排序(Heap Sort)是一种高效的原地排序算法,它巧妙地利用了“堆”数据结构。其核心思想是首先将待排序的数组重构成一个最大堆(Max Heap)。在最大堆中,根节点(数组的第一个元素)始终是所有元素中的最大值。
构建好最大堆后,算法将堆顶的最大元素与堆末尾的元素交换,从而将当前的最大值放置到数组的正确最终位置。接着,将堆的大小减一,并对剩余的元素进行“堆化”调整,确保新的根节点仍然是剩余元素中的最大值。此过程不断重复——交换、缩小堆、重新堆化——直到所有元素都被放置到其最终的有序位置,完成整个排序。
堆(Heap)是一种特殊的完全二叉树结构,它的两个重要特性:
- 堆是一个完全二叉树,除了最底层外,其他层的节点都是满的,最底层的节点从左到右填充。
- 在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都小于或等于其子节点的值。
堆的数组表示:
虽然堆是一种树结构,但是也可以用数组高效地表示,这是堆的一个重要特性。
对于数组中索引为 i 的节点:
其左子节点的索引为 2*i + 1
其右子节点的索引为 2*i + 2
...
