Heap_size in heap_sort

Question

我正在阅读Cormen的“算法简介”，我正在尝试实现堆排序，但有一件事我一直无法理解:我们如何计算给定数组的heap_size？我的教科书上说

表示堆的数组A是一个具有两个属性的对象: A.length (和往常一样)给出数组中的元素数；A-堆大小，它表示堆中存储在数组A中的元素的数量。也就是说，尽管A1。A.length可以包含数字，只有A1.A堆大小中的元素，其中0 <= A堆大小<= A.length是堆的有效元素。

如果我将一个数组实现为std::vector<T> Arr，那么它的‘大小将是Arr.size，但是它的’heap_size‘是什么？

Answer 1

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

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

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