堆积排序是另一种形式的选择排序。它涉及到 堆积 和 完全二叉树 的概念。
1. 堆积的定义
具有n个数据元素的序列 K = (k1, k2, k3, k4, . . . , kn); 当且仅当满足条件
k[ i ] >= k[ i*2 ] && k[ i ] >= k[ i*2+1]
或者
k[ i ] <= k[ i*2] && k [ i] <= k[ i*2+1]
i = (1, 2, 3, 4, . . . , n/2)
时称序列K为一个堆积(heap),简称堆。有时将满足第一种条件的堆积称为大顶堆积,满足第二种条件的堆积称为小顶堆积。大顶堆积的第一个元素具有最大值。下面的讨论针对大顶堆积而言。
若将序列的元素依次存......
阅读全文