我查看了C++ 0x标准,发现要求make_heap不应超过3*N比较.
即堆积无序集合可以在O(N)中完成
/* @brief Construct a heap over a range using comparison functor.
为什么是这样？
来源没有给我任何线索(g ++ 4.4.3)
while(true)+ __parent == 0不是线索,而是对O(N)行为的猜测
template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
const _DistanceType __len = __last - __first;
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
_ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
__comp);
if (__parent == 0)
return;
__parent--;
}
}
__adjust_heap看起来像一个log N方法:
while ( __secondChild < (__len - 1) …我遇到了以下非常困难的面试问题：
考虑具有三个操作的队列数据结构：
Run Code Online (Sandbox Code Playgroud)- Add into the front of list (be careful front of list) - Delete from Tail of the list (end of the list) - Extract Min (remove)
此数据结构的最佳实现已摊销时间：
A) O(1) 的三个操作
B) 三个 O(log n) 的操作
C) 在 O(1) 中添加和删除，在 O(log n) 中提取最小
D) 在 O(log n) 中添加和删除，在 O(n) 中提取最小
面试后我看到（C）是正确答案。为什么会这样？
第一个挑战是比较选项：哪个选项比其他选项更好，我们如何理解最终的正确选项？
许多数据结构使用称为"左子,右兄弟"表示的表示将多路树存储为二叉树.这是什么意思？你为什么要用它？
的斐波那契堆数据结构在其名称中的"黄金分割",但没有在数据结构似乎使用斐波那契数.根据维基百科的文章:
Fibonacci堆的名称来自Fibonacci数字,用于运行时间分析.
Fibonacci堆中如何出现这些Fibonacci数？
有人可以解释一下我应该如何决定是否使用一个或另一个堆实现,在标题中提到的那些？
根据问题,我想要一个答案来指导我选择有关结构性能的实施方案.现在,我正在做一个优先级队列,但我想知道这个案例最合适的实现,但是基本允许我在任何其他情况下选择一个实现...
另外需要考虑的是我这次使用的是haskell,所以,如果你知道任何可以改善这种语言实现的技巧或其他东西,请告诉我!但和以前一样,欢迎使用其他语言的评论!
谢谢!对不起,如果问题太基础,但我根本不熟悉.这是我第一次面临实施一项任务的任务......
再次感谢!
algorithm ×2
binary-heap ×2
fibonacci ×2
big-o ×1
binary-tree ×1
c++ ×1
haskell ×1
math ×1
performance ×1
stl ×1
tree ×1