堆排序.pptVIP

堆排序 堆的定义 堆的建立 堆的删除 堆排序 回顾 满二叉树 二叉树的所有分支结点都有左子树和右子树，并且所有叶子结点都在二叉树的最下一层； 完全二叉树 具有n个结点的完全二叉树，它的结构与满二叉树的前n个结点的结构相同； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 深度为h的完全二叉树：前h-1层为满二叉树，最后一层的结点必须从左向右连续出现。 对于具有n个结点的完全二叉树，如果按照从上至下，每层从左至右的次序，对结点进行编号，则编号为i的结点有以下性质： 若i≤ ? n/2 ? , 即2i≤n,则编号为i的结点为分支结点，否则为叶子结点 若n为奇数，则树中每个分支结点既有左孩子又有右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有 若编号为i 的结点有左孩子，则左子结点的编号为2i；若编号为i的结点有右孩子则右子结点为2i+1 除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为? i/2 ? 回顾 堆的定义 n个元素的序列{k1,k2,…,kn}当且仅当满足如下关系时，称之为堆（heap）。若满足条件（1）则称大根堆（或大顶堆）；若满足条件（2）则称小根堆（或小顶堆）。 若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 大根堆示例 87 78 53 45 65 09 31 17 23 1 2 3 4 5 6 7 8 9 堆顶元素值最大 87 78 53 45 65 09 31 17 23 1 2 3 4 5 6 7 8 9 小根堆示例 9 17 65 23 45 78 87 53 31 1 2 3 4 5 6 7 8 9 堆顶元素值最小 9 17 65 23 45 78 87 53 31 1 2 3 4 5 6 7 8 9 堆的建立（以大根堆为例） 将给定的序列看成是完全二叉树的按层次遍历结果，并建立对应的完全二叉树； 从最后一个非终端结点（i=n/2）开始，依次调整每一棵子树为大根堆。（自下向上逐步调整为堆） 对第i个关键字进行筛选的要点： 在第2i个结点和第2i+1个结点中（左右孩子）选大者定为X； 若第i个结点（根）小于X则二者交换； 交换后还须考虑以2i为根或以2i+1为根的子树是否仍然是堆，若不是则需要继续向下调整； 【例1】将10个元素组成的序列{ 34, 39, 20, 65, 47, 12, 98, 73, 81, 56 }建成大根堆。 将序列看成是完全二叉树的按层次遍历结果，建立完全二叉树； 自下向上将完全二叉树调整为大根堆（动画演示） 堆的删除——删除堆顶元素 将堆尾元素写入堆顶； 自上而下调整受影响的子树，使每一棵有变动的子树都符合堆的要求； 如果调整后改变了的子树的根结点，则继续调整相应的子树直到堆的叶子结点。 【例2】删除堆顶元素98 98 34 81 20 12 56 73 39 65 47 47 34 81 20 12 56 73 39 65 81 34 47 20 12 56 73 39 65 81 34 73 20 12 56 47 39 65 81 34 73 20 12 56 65 39 47 直接选择排序 基本思想：将数据元素序列分成有序区和无序区两部分。每趟排序都从无序区中选取出关键字最小的数据元素放在有序区的最后，直到全部数据元素排序完毕。 要点： 把元素集合划分为有序区和无序区 初始时，有序区为空 每趟排序过程中，从无序区中选出关键字最小的数据元素与无序区的第一个元素交换，以达到扩大有序区长度的目的。 回顾 堆排序 堆排序(HeapSort)是一树形选择排序，利用大根堆(或小根堆)堆顶元素最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 堆排序的一般步骤（以结果为非递减序列为例） 将待排序序列R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，创建对应的完全二叉树； 将第①步创建的完全二叉树调整为小根堆； 利用小根堆的特性，从堆中提取最小值并删除根； 重新调整删除根的堆为新堆，重复第③步直到堆的长度为零； 将每次提取的根依次排列即为有序序列。 【例3】用堆排序将序列{ 20, 60, 26, 30, 36, 10 } 调整为递增序列。 构建小根堆； 提取堆顶并调整删除堆顶后的元素为新堆； 重复第2步，直至堆空。 每次提取的堆顶依次排列即为递增序列。 将序列{ 20, 6