标签: binary-heap

我愿意使用数据结构作为常量空间的溢出缓冲区.我希望有效插入,但最重要的是有效去除min元素.我正在考虑使用堆,因为我有O(log(n))find_min()和log(n)插入和删除.另一方面,我知道不了解与红黑树相比的优势,因为它也有O(log(n))插入和删除但O(1)找到最小/最大.并排序输出的优势(我不关心).

问题与:红黑树是我理想的数据结构吗？

由于我从std :: map和boost :: heap可以获得这两个结构,为什么我更喜欢使用堆而不是红黑树呢？最后,使用红黑树我也有一个条目的O(log(n))搜索时间,而对于一个堆,时间是O(n),这是重要的,因为存在重复.

我认为我知道答案,最小的复杂性是O(nlogn).

但是,有没有什么办法可以在O(n)复杂度中从堆中创建二进制搜索树？

在(最大)堆中,很容易及时找到最大的项目O(1),但要实际删除它,您需要复杂性O(log(n)).

因此,如果从堆中插入和删除两者O(log(n)),堆超过二叉树表示优先级队列的优点是什么？

请帮助识别此 B 堆中的模式：

在正常的二叉堆中，我们总是使用以下条件：left_child = 2*i, right_child = 2*i+1 parent = i/2

但是这些条件只适用于前 2 个级别，我无法识别剩余的模式。请帮我。

我可以使用std::collections::BinaryHeap以最大到最小顺序迭代结构集合pop,但我的目标是从最小到最大迭代集合.

我通过颠倒Ord实现成功了:

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.offset {
            b if b > other.offset => Ordering::Less,
            b if b < other.offset => Ordering::Greater,
            b if b == other.offset => Ordering::Equal,
            _ => Ordering::Equal, // ?not sure why compiler needs this
        }
    }
}

现在BinaryHeap返回的Items至少是最大的.看到这不是预期的API,这是一个不正确或容易出错的模式吗？

我意识到a LinkedList会给我这个pop_front方法,但是我需要在insert上对列表进行排序.这是更好的解决方案吗？

我正在寻找一种在二进制堆（最大或最小）上实现迭代器的方法。

也就是说，通过第i次使用其nextNode（）函数，可以获得堆中第i个（更大或更小的）元素。

请注意，此操作是在没有实际提取堆根的情况下发生的！

我最初的想法是：

• 实际上提取i元素，将它们压入堆栈，然后在获得第i个值后将它们重新插入堆中。每个函数调用都需要O（i * log（n））。
• 保留一个辅助排序的数据结构，该结构可以允许在O（1）中查找下一个值，但是更新将占用O（n）。

我了解这些方法消除了使用堆的好处，因此我正在寻找一种更好的方法。

我已经坚持了一段时间的问题,并想知道是否有人可以指出我正确的方向:

假设使用基于指针的树表示而不是数组来表示二进制堆.考虑将二进制堆LHS与RHS合并的问题.假设两个堆都是完整的完整树,分别包含(2 ^ L - 1)和(2 ^ R -1)个节点.
给两个O(log N)算法合并两个堆,一个是L = R,一个是| L - R | = 1.

这是一个家庭作业问题,我只需要指出正确的方向.

我只是想学习二进制堆,并对在二进制堆中执行删除操作有疑问.我已经读过我们可以从二进制堆中删除一个元素,我们需要重新封装它.

但在以下链接中,它表示不可用:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

                Binary Search  AVL Tree   Binary Heap (min)  Binomial Queue (min)

Find            O(log n)       O(log n)   unavailable         unavailable
Delete element  O(log n        O(log n)   unavailable         unavailable

我对此感到困惑.

提前感谢所有澄清.

假设我们有一个包含n个元素的二进制堆,并希望插入n个更多的元素(不一定是一个接一个).这需要的总时间是多少？

我认为这是theta(n logn),因为一次插入需要登录.

最初的问题是给出了前一天访问过的5GB URL的文件,找到了前k个常用URL.这个问题可以通过使用哈希映射计算不同URL的出现来解决,并在min heap的帮助下找到前k个,获取O(n log k)时间.

现在我在想如果输入是无限的在线数据流(而不是静态文件),那我怎么知道最后一天的前k个URL呢？

或者我是否可以对系统进行任何改进,使我能够动态地获取最后一分钟,最后一天和最后几小时的前k个URL？

任何提示将不胜感激!