我可以只使用percolateDown来实现一个堆吗？

我需要在C中实现堆数据结构。我在做一些研究时，看到有人用buildHeap（），constructHeap（）将数组转换为堆。我的问题是，每次需要添加堆时，我可以在新添加的项目上调用percolateDown（）而不是实现这些功能？我可以只使用percolateDown来实现一个堆吗？

谢谢！

2012-10-01 Dino55

堆可以在线性时间内构建，而您提出的方法需要O（N log（N））时间。更好地在单独的函数中构造堆以获得更好的性能。

2012-10-01 06:53:10

即使我没有一个数组开始？我打算在需要时将项目添加到堆中。谢谢！ – Dino55

@ Dino55 - 如果你逐个添加元素，你当然没有比逐个添加元素更好的选择。你的问题是“为什么有构造堆方法”。答案是因为从一个数组构造堆可以比逐个添加数组的元素的复杂性更好。 –

即使您逐个添加元素，如果您需要在添加元素之间使堆不变为真，则每次只需调用'percolateDown'。 build/construct用于数组不需要成为堆的情况，直到在它有几个元素之后。如果那不是你的情况那就够公平了。 –

回答