Chi*_*ffa 1 c++ arrays algorithm heapsort
我正在阅读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是什么目前超出我的范围.
堆大小应该是一个单独存储的变量,您自己管理.
每当从堆中删除或添加时,都应该适当地减小或增加该值.
在C++中,使用a vector,你实际上可以使用size,因为底层表示是一个至少与向量大小一样大的数组,并且如果你resize用较小的大小调用它保证保持相同的大小.(因此底层数组将是数组大小,矢量大小将是堆大小).