c++ - heap_sort 中的 heap_size

Question

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

表示堆的数组 A 是一个具有两个属性的对象：A.length，（通常）给出数组中元素的数量，以及 A.heap-size，表示堆中存储了多少元素数组 A。也就是说，虽然 A[1 .. A.length] 可能包含数字，但只有 A[1..A.heap-size] 中的元素，其中 0 <= A.heap-size <= A.length , 是堆的有效元素。

如果我将一个数组实现为std::vector<T> Arr，那么它的大小将是Arr.size，但它的 heap_size 目前是什么超出了我的范围。

Answer 1

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

每当您从堆中删除或添加时，都应该适当地减少或增加该值。

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