c++ - 堆排序中的堆大小

Question

我正在阅读 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 是多少目前超出了我的范围。

Answer 1

堆大小应该是一个单独存储的变量，您自己管理。

无论何时从堆中删除或添加到堆中，都应该适本地减少或增加值。

在 C++ 中，使用 vector，您实际上可以使用 size，因为底层表示是一个至少与大小一样大的数组 vector ，如果您以较小的尺寸调用 resize，它保证保持相同的尺寸。 (因此底层数组将是数组大小， vector 大小将是堆大小)。