堆类型实现

Question

我正在实现一个堆排序，我开始想知道堆的不同实现。当您不需要按索引访问元素时(就像在堆排序中一样)，使用数组实现堆或像其他链接数据结构一样实现堆有什么优缺点。

我认为重要的是要考虑到节点和指针所浪费的内存与数组中空格所浪费的内存，以及在必须调整数组大小时添加或删除元素所需的时间。

我应该在什么时候使用每一个，为什么？

Answer 1

就空间而言，如果提前知道有多少数据进入堆中，那么使用数组几乎没有问题--堆中的值总是指向较大结构的指针。这可能会在堆本身上实现更好的缓存本地化，但您仍然需要到内存中去获取额外的数据。理想情况下，如果您的比较是基于一小部分数据(通常只是一个4字节的浮点数或整数)，您可以将其存储为带有指向整个数据的指针的键，并实现良好的缓存一致性。

然而，堆排序对于遍历堆结构本身的缓存命中来说已经不是特别好了。对于完全放在L1/L2缓存中的小堆来说，情况并不是那么糟糕。然而，当你开始命中主存的时候，性能会一落千里。通常这不是问题，但是如果有问题，合并排序是你的救星。

当你想要一个大小不确定的堆时，更大的问题就来了。然而，即使使用数组，这仍然不是那么糟糕。此外，在非嵌入式环境中，使用漂亮的内存系统通过一些调用(例如realloc，请原谅我的C背景)来增长一个数组并不是那么慢，因为数据可能不需要物理地在内存中移动--只需要一些地址指针魔术。此外，如果您使用数组大小加倍策略(数组太小，是realloc调用中大小的两倍)，您最终仍然会得到O(n)的摊销成本，而reallocs相对较少，最多浪费两倍的空间--但是嘿，如果您使用的是32位键和32位指针，那么您无论如何都会在链表中得到这样的结果。

因此，简而言之，对于较小的基本数据结构，我坚持使用数组。当堆消失时，我不再需要的指针也随之消失，只需释放一次。然而，在我看来，阅读堆的基于指针的代码更容易，因为处理索引魔术并不是那么简单。如果性能和内存不是一个问题，我会建议任何人在心跳。