如何构建二叉树最大堆.

这实际上是堆排序问题. 首先是将序列构建到堆中.

将无序序列构建到堆中的过程实际上是重复筛选的过程. 如果将此序列视为完整的二叉树，则最后一个非终端节点为[n / 2]（不大于n / 2的整数）二叉排序树 堆二叉排序树 堆，因此筛选过程仅需从[n / 2]开始. 要构建大的顶桩，请首先选择值最大的元素，然后将其与序列中的最后一个元素交换，然后在序列之前过滤n-1个元素，并重新调整为大的顶桩，直到末端.

算法描述如下:

typedefint [] Elem; //使用顺序存储来表示完整的二叉树

voidHeapAdjust（Elem＆e，ints，intm）

{// s ... m的e元素满足了堆的定义，除了e [s]（e [i] <= e [2 * i] && e [i] <= e [2 * i + 1]

//或e [i]> = e [2 * i] && e [i]> = e [2 * i + 1]），调整e [s]，使e [s ... m]变为一大堆.

selem = e [s];

for（i = 2 * s; i <= m; i * = 2）//沿具有较大值的元素（节点）向下过滤

{

if（i

if（selem> = e [i]）break;

e [s] = e [i];

s = i;

}

e [s] = selem;

}

voidHeapSort（Elem＆e）

{//排序顺序表

for（i = e.length / 2; i> 0;-i）

HeapAdjust（e，i，e.length）;

for（i = e.length; i> 1;-i）

{

temp = e [1]; //将堆中的最后一个元素与第一个元素交换

e [1] = e [i];

e [i] = temp;

HeapAdjust（H，1，i-1）; //调整1..i-1的元素以使其成为大的顶部堆

}

}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-257142-1.html