堆积排序

堆积的定义:

具有N个数据元素的序列K=(k₁,k₂,k₃,...k_n),当且仅当满足条件

ki≥k2i且ki≥k2i+1   大顶堆

或者ki≤k2i且ki≤k2i+1 小顶堆

(i=1,2,...)

时称序列K为一个堆积(heap)，简称堆

堆积可以和一个完全二叉树相对应

堆积排序的基本的思想:

1)       建立初始堆积。

2)       交换堆积的第一个元素(即最大或最小的元素)和最后一个元素的位置。

3)       将移走最大或最小元素之后的剩余元素组成的序列在转化成一个堆积。

4)       重复上述过程第二步到第三步n-1次。

建立初始堆积的过程是从下到上依次进行调整，要调整次

2)到3)的n-1的迭代是从上向下进行调整

例（26，5，77，1，61，11，59，15，48，19）

最后调整成的堆积是

(77，61，59，48，19，11，26，15，1，5)