如何建立堆(给出大根堆和小根堆的源程序,要PASCAL的)

Proceduresift(i,m:integer){调整以i为根的子树成为堆,m指前m个结点}

vart,k:integer

begin

t:=a[i]

k:=2*i{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}

whilek<=mdo

begin

if(k<m)and(a[k]<a[k+1])theninc(k){找出a[k]与a[k+1]中较大值}

ift<a[k]then{选取最大根}

begin

a[i]:=a[k]

i:=k{修改i,k的值，以便继续向下筛选}

k:=2*i

end

elsek:=m+1{筛选完成，以便终止循环}

end

a[i]:=t{将根放在合适的位置}

end

Procedureheapsort

var

i:integer

begin

fori:=ndiv2downto1dosift(i,n){用数组模拟二叉树建堆}

fori:=ndownto2do{从大到小输出}

begin

write(a[1],’‘)swap(a[1],a[i]){a[1]:=a[i]}

sift(1,i-1)

end

writeln(a[1])

end

小根堆改改就出来了。

堆排序，也叫二叉堆排序。

完全二叉树：

1、左右子树的节点数满足 Ln/Rn=1

2、左右子树高度满足 Rh+1>=Lh>=Rh

3、子节点值统一比父节点大（小）。

最大堆：2叉树的所有子节点都比父节点小。所以根节点是最大的。

最小堆：2叉树的所有子节点都比父节点大。所以根节点是最小的。

建堆：假设最多有N个数据。开辟一段用来存这N个数据的空间。根节点位置为0。其子节点位置为1、2。所有子节点位置与父节点的位置（k）关系：k，2k+1，2k+2。 假设已经有了n个数据，那么新数据自然放在n位（因为位置是从0开始），定义一个函数 shift_up() 用来调整新数据。它的功能是：将新数据与 (n-1)/2 位置的数据（新数据的父节点）比较，如果比父节点大，那么就交换，继续比较，直到它比父节点小。

重新建堆： 当取数据时，就是将根节点取出来。因为根节点是最大的，所以自然还要将其所有子节点进行调整，以保证剩下的数据的根节点是最大的。方法是：将最后一个数放到根节点位置（因为根节点取出后，根节点就空了），然后调用 shift_down()函数将其与1、2位置的数比较，如果比它大，则交换，然后继续与2k+1，2k+2位置的比较，直到这两个位置的数都比它小。

---