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

Question

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

谢谢！

Answer 1

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