数据结构与算法(Python语言描述)课件DS_053_优先级队列和堆排序讲解.ppt

堆排序HeapSort * step1：对序列建堆； step2： 不断输出堆顶元素，然后通过siftdown再次调整成元素数少1的堆，直到所有元素输出。 堆结构的应用——堆排序 * 堆排序 * 小顶堆排序的结果是由大到小！ 堆排序 def heap_sort(elems): def siftdown(elems, e, begin, end): # [begin, end) i, j = begin, begin*2+1 while j end: if j+1 end and elems[j+1] elems[j]: j += 1 if e elems[j]: break elems[i] = elems[j] i, j = j, 2*j+1 elems[i] = e end = len(elems) for i in range(end//2-1, -1, -1): # 初始建堆 siftdown(elems, elems[i], i, end) for i in range((end-1), 0, -1): # 不断输出堆顶，然后调整 e = elems[i] elems[i] = elems[0] # 堆顶输出后，放到当前的最后 siftdown(elems, e, 0, i) # 注意：堆的范围在缩小 时间：O(n logn) 建堆：O(n) 不断输出堆顶、调整： O(n logn) 共n个元素 每个元素输出后的siftdown，不超过树的深度 log(n-1) + … + log(2) n logn 空间：O(1) 堆排序的复杂度分析 * 小结 * 堆结构的特点 逻辑上是“基本有序”的完全二叉树，小顶堆堆顶最小！ 堆调整 Siftup——小数上浮，将大的双亲挤下来； Siftdown——大数下沉，将小孩子挤上去； 建堆 过程：自后向前不断siftdown，逐步合成一个大堆 O(n) 堆排序 方法：不断输出堆顶，回填后再siftdown O(nlogn) 要求掌握！ * 大顶堆 和 小顶堆 堆顶的“优先级”最高 【数最小 ~~ 小顶堆】 上面轻，下面沉； 上面气泡，下面石头 气泡上浮，石头下沉 “土堆” * 堆 是一棵“基本有序”的完全二叉树 ！ 任何结点的值都小于等于其左右孩子的值！ 堆（递归定义） 空树； 若非空，是一棵完全二叉树，满足： 若根结点有左孩子，则根结点值小于等于其左孩子值； 若根结点有右孩子，则根结点值小于等于其右孩子值； 左右子树仍然是堆！ 特点： 最优先的元素位于堆顶； 左右子树仍然是堆； 由根到叶子的路径上，结点是有序的； 应用： 表示优先级队列！ 堆排序 堆 * 堆的表示 * 适合顺序存储 结点i 的孩子： 2 * i + 1， 2 * i + 2 结点i 的双亲： ?( i -1 )/2? 由根到叶子的路径长 ~ logn 含有n个结点的完全二叉树的深度： ? log2n ? 回忆：完全二叉树的性质 * 堆的表示 顺序存储！！！ 0 1 2 3 4 5 6 7 12 36 24 85 47 30 53 91 含n个元素的线性序列elem[0,…n-1]，满足： elem[i] = elem[2 * i + 1]， 如果2*i+1 n elem[i] = elem[2 * i + 2]， 如果2*i+2n 堆的另一种定义 * 0 1 2 3 4 5 6 7 12 36 24 85 47 30 53 91 存储上：线性结构 逻辑上：完全二叉树（层次结构） 对堆结构的理解 * 堆的维护——插入删除 * 如何向堆中插入元素？？？ * 0 1 2 3 4 5 6 7 12 36 24 85 47 30 53 91 25 尾部插入元素后的siftup 12 36 24 30 47 85 53 91 25 12 36 24 30 47 25 53 91 85 12 25 24 30 47 36 53 91 85 siftup——从尾部开始沿双亲上行 * j = (last-1