我正在阅读 Cormen 的“算法导论”,我正在尝试实现堆排序,但有一件事我一直无法理解:我们如何计算 heap_size
对于给定的数组?
我的教科书说
An array A that represents a heap is an object with two attributes: A.length, which (as usual) gives the number of elements in the array, and A.heap-size, which represents how many elements in the heap are stored within array A. That is, although A[1 .. A.length] may contain numbers, only the elements in A[1..A.heap-size],where 0 <= A.heap-size <= A.length, are valid elements of the heap.
如果我将数组实现为 std::vector<T> Arr
, 那么它的大小就是 Arr.size
,但它的 heap_size 是多少目前超出了我的范围。
最佳答案
堆大小应该是一个单独存储的变量,您自己管理。
无论何时从堆中删除或添加到堆中,都应该适本地减少或增加值。
在 C++ 中,使用 vector
,您实际上可以使用 size
,因为底层表示是一个至少与大小一样大的数组 vector ,如果您以较小的尺寸调用 resize
,它保证保持相同的尺寸。 (因此底层数组将是数组大小, vector 大小将是堆大小)。
关于c++ - 堆排序中的堆大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19292396/