如何按排序顺序打印堆而不更改它？

Question

我想按排序顺序打印一个堆（从最小到最大），但不要改变堆。 我知道我可以做一个临时数组的remove_min并打印，直到它为空并插回去。 有没有更好的方法？

Answer 1

最简单的方法是制作堆的副本，然后从副本中移除remove_min。 （这与HeapSort的后半部分基本相同。）

清空原始堆，然后重新填充它，将更改堆元素的内部排序。虽然这不会对堆的外部行为产生任何明显的影响（除了使未来的remove_min稍微快一点），它在技术上仍然是“改变堆”。