堆排序问题
由于堆是二叉树和数组的组合，那么排序时整个堆是否保持完整树的形式？
对于家庭作业，我必须跟踪排序的每个步骤的堆和数组，并且我不确定树的表示形式。
As a heap is a combination of a binary tree and array, when sorting does the entire heap keep the form of a complete tree?
For a homework assignment, I have to trace out the heap and array for each step of the sort, and I'm not sure of the tree representation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
堆始终是完美平衡的完全填充树，遵循堆不变量 - 对于最小堆，节点的值始终大于或等于其每个子节点的值。
堆排序用未排序的数据创建一个堆（O(n) 时间），然后重复删除堆的顶部元素（O(lg n) 时间，因为每次删除都必须维护堆）并将其放入数组中。值得注意的是，这只有在保持堆不变的情况下才有效——除了其他亮点之外，这还需要完美的平衡和有效的树。
二叉树并不是堆最有效的表示形式； 关于二进制堆的维基百科文章很好地解释了如何使用数组来表示一个。 有关堆排序的文章提到了一个有用的细节：您可以通过使用如果使用数组表示，则位于堆的末尾来构建输出数组，因为堆始终保持平衡，并且删除元素最终将释放表示堆的数组的物理最后一个单元格。
A heap is always a perfectly-balanced fully-populated tree that follows the Heap Invariant- for a min-heap, a node's value is always greater than or equal to the value of each of its children.
Heapsort creates a heap out of unsorted data (O(n) time), then repeatedly removes the top element of the heap (O(lg n) time because the heap has to be maintained with each removal) and puts it into an array. Notably, this only works if it keeps the heap invariant- which requires, among other highlights, perfect balancing and a valid tree.
The binary tree isn't the most efficient representation of a heap; the Wikipedia article on binary heaps explains very well how to use an array to represent one. The article on Heapsort mentions a useful detail: you can sort in place, by using the space off the end of the heap, if using the array representation, to build your output array, because the heap always balances and removing an element will eventually free up the physically last cell of the array representing the heap.