数据结构课件 第三章 堆排序与基数排序.ppt

3.3.3 堆排序Heap Sort 1堆的定义 n个关键字序列KlK2Kn称为堆当且仅当该序列满足如下性质(简称为堆性质) (1) Ki K2i 且 Ki K2i+1 小顶堆 或 (2) Ki K2i 且 Ki K2i+1 大顶堆 (1in/2) 若将此序列所存储的向量R[1.n]看做是一棵完全二叉树的存储结构则堆实质上是满足如下性质的完全二叉树 树中任一非叶结点的关键字均不大于(或不小于)其左