数据结构第8章 排序 (3).ppt

8.4.2 堆排序 堆的定义n个关键字序列k1k2kn成为堆当且仅当该序列满足如下性质简称为堆性质 1 kik2i且kik2i+1或 2 kik2i且kik2i+11i |n/2| 满足第1中情况的成为小根堆 满足第2种情况的成为大根堆下面讨论的堆是大根堆 8.4.2 堆排序 堆排序的排序过程设有n个元素首先将这n个元素按关键字建成堆将堆顶元素输出得到n个元素中关键字最小(或最大)的元素然后再对剩