数据结构&算法实践—堆排序

596 查看

排序>>选择排序>>堆排序

List:

  1. start

基本概念:

维基百科http://zh.wikipedia.org/zh-cn/%E5%A0%86%E7%A9%8D%E6%8E%92%E5%BA%8F

堆为一棵完全二叉树,每个节点值都>=子节点值

堆排序根据这个特性,首先将所有元素建立堆,然后一个个取出,即有序的

堆中每个节点的位置:

最大堆主要操作逻辑:

插入:将新元素加入完全二叉树最后一个节点,依次往上,调整直到满足父节点值都>=子节点值

删除:移除根节点,将最后一个节点拿到根节点,依次往下,调整

原始:

heap1

插入操作:12,先假定放在最后一个位置,然后从这个节点开始往上,同父节点比较,依次调整

heap2

删除:取走11,将最后一个元素8移到根节点,从上往下,重新调整

heap3

  1. start

根据公式,我们可以使用数组模拟实现完全二叉树(不使用首个位置)

首先,我们先实现堆:

然后,实现排序过程:

  1. start

A.概念,过程描述?

B. 时间复杂度?空间复杂度?是否是稳定排序?

C.适用场景,何种情况下表现最优