堆排序代码解析 堆排序的算法及代码实现

目前这个系列的文章都挑着非常经典的,让人眼前一亮的算法,今天的堆排序算法就是其中一个 。首先理解什么是堆,这里面堆(Heap)并不是程序中内存区域,而是一种完全二叉树表示的数据结构 。堆具有以下特点

  • 是一个完全二叉树
  • 堆的每个节点的值必须大于等于左右树节点(大顶堆),或小于等于左右树节点(小顶堆) 。
简单说明下,完全二叉树是除了最后一层叶子节点外,其他的节点都有两个子树,而叶子节点可以没有子树,或者只有左子树 。如下图就是个大顶堆:

堆排序代码解析 堆排序的算法及代码实现



堆排序代码解析 堆排序的算法及代码实现


小顶堆

堆排序代码解析 堆排序的算法及代码实现


堆存储
堆因为是完全二叉树,非常适合用数组存储,上图为大顶堆的存储情况,其中a[0]不用,a[1]为大顶堆的顶点,也就是最大的数据,a[1

    推荐阅读