堆排序(上)

Monday, May 6, 2019

堆是一种特殊的树

  • 堆是一个完全二叉树
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树每个节点的值

file

1,2是大顶堆,3是小顶堆,4不是堆。

堆的实现

同之前一样,完全二叉树适合用数组存储,堆同理。

file

往堆中插入元素

file

当我们把元素插到最后时,实际就不满足堆的特性了,这时我们需要进行堆化。 堆化就是向上或者向下,顺着节点所在的路径进行比对,然后交换。

file

删除堆顶元素

因为堆的定义我们可以知道,堆顶元素就是堆中最大或者最小的值。

file

但是这样操作会有问题,就是最后堆化完之后不是完全二叉树了。

我们可以换一种思路,把最后一个节点放到堆顶,然后用父子节点比对方法,再互换节点,直到所有节点满足大小关系。

file

堆排序

堆的排序时间复杂度是O(nlogn),而且是原地排序算法。

建堆

我们将数组原地建成一个堆,思路是从后往前处理数组,并且每个数据都是从上往下堆化。

file

file

我们对下标n/2开始到1的数据进行堆化,下标n/2 + 1到n的节点是叶子结点,不需要堆化。

建堆的时间复杂度是O(n)

排序

建堆之后,数组中的数据已经是按照大顶堆特性来组织,数组的第一个元素就是最大的元素,我们把最后一个元素跟它交换,最大的元素就放到了下标为N的位置,然后以此类推,将后面的元素进行堆化,直到最后堆中只剩下下标为1的元素,排序就完成了。

file

为什么快排比堆排性能好

  • 堆排数据访问的方式没有快排好
  • 同样的数据,堆排的数据交换次数要多于快排
数据结构-算法

图的表示

二叉树基础(下)