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

Question

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

谢谢!

Answer 1

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