育才学习网小根堆怎么写
1. 什么叫堆
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。
最大堆和最小堆是二叉堆的两种形式。
最大堆（大根堆）：根结点的键值是所有堆结点键值中最大者。
最小堆（小根堆）：根结点的键值是所有堆结点键值中最小者。
而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。
扩展资料
在考虑将以Ki为根的子树排成堆时，以Ki+1,Ki+2，…，Kn-1为根的子树已经是堆，所以这时如果有Ki≤K2i+1和Ki≤K2i+2，则不必改变任何结点的位置，以Ki为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后Ki的值必定是原来K2i+1和K2i+2中较小的一个。
不妨假定K2+1较小，将Ki与K2i+1交换位置，这样调整后Ki≤K2i,Ki≤K2i+1，并且以K2i+2为根的子树原来已经是堆，不必再作任何调整，只有以K2i+1为根的子树由于K2i+1的值已经发生变化（与Ki交换了），所以有可能不满足堆的定义（当K2i+1的左、右子树已经是堆）。
这时可重复上述过程，考虑将K2i+1以为根的子树排成堆。如此一层一层递推下去，最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。它就像过筛一样，把最小的关键码一层一层选择出来。
参考资料来源：搜狗百科-最小堆
2. 如何建立堆（给出大根堆和小根堆的源程序,要PASCAL的）
Procedure sift(i,m:integer)；{调整以i为根的子树成为堆，m指前m个结点}
var t,k:integer;
begin
t:=a[i];
k:=2*i；{在完全二叉树中结点i的左孩子为2*i，右孩子为2*i+1}
while k<=m do
begin
if (k<m) and (a[k]<a[k+1]) then inc(k)；{找出a[k]与a[k+1]中较大值}
if t<a[k] then {选取最大根}
begin
a[i]:=a[k];
i:=k； {修改i,k的值，以便继续向下筛选}
k:=2*i;
end
else k:=m+1；{筛选完成，以便终止循环}
end;
a[i]:=t； {将根放在合适的位置}
end;
Procedure heapsort;
var
i:integer;
begin
for i:=n div 2 downto 1 do sift(i,n)； {用数组模拟二叉树建堆}
for i:=n downto 2 do {从大到小输出}
begin
write(a[1],' '); swap(a[1],a[i]);{a[1]:=a[i]}
sift(1,i-1);
end;
writeln(a[1]);
end;
小根堆改改就出来了。
转载请注明出处育才学习网 » 小根的根怎么写