10.4.2堆排序排序思路1.全局有序区无序区选出最小元素R[k]采用堆方法选出最小元素：堆排序算法11/36
1. 排序思路 全局有序区 无序区 选出最小元素R[k] 采用堆方法选出最小元素：堆排序算法 11/36
堆的定义一个序列R[1..n]，关键字分别为k1、k2、...、kn。该序列满足如下性质（简称为堆性质）：k,≤k2i 且k,≤k2i+1(1≤i≤Ln/2])或 @ k,≥k2i 且k;≥k2i+1满足第○种情况的堆称为小根堆，满足第②种情况的堆称为大根堆。下面讨论的堆是大根堆。12/36
一个序列R[1.n]，关键字分别为k1、k2、、kn。 该序列满足如下性质（简称为堆性质）： ki≤k2i 且ki≤k2i+1 或 ki≥k2i 且ki≥k2i+1 （1≤i≤n/2） 满足第种情况的堆称为小根堆，满足第种情况的堆称为大根堆。下 面讨论的堆是大根堆。 12/36