0

所以我有一个执行堆排序的程序，并且我有一个删除元素功能。我通过将最后一个元素一直放在右侧，然后用它替换第 n 个元素来做到这一点。为了保持排序，然后我将元素冒泡到堆中的正确位置。我的朋友似乎不认为这会奏效。会吗？

4

1 回答 1

0

Heapsort使用的是max-heap，每次都需要将最大的根节点与第nth元素进行切换，然后将最大的元素从右到左放入结果列表中。

然后，将元素冒泡到适当的位置，并将堆的大小从 n 减小到 n-1。

那么，新堆的新根节点就是剩余n-1个元素中的最大元素。只需递归切换根元素与第n-1th 元素，并再次将最大元素放入结果列表，将堆的大小减 1，直到堆的大小为 0

于 2012-12-07T06:16:17.287 回答