我们可以用二叉搜索树模拟堆操作？ [英] Can we use binary search tree to simulate heap operation?

问题描述

我在想，如果我们可以用一个二叉搜索树模拟堆操作（插入，找到最低，删除最小），即，使用BST做同样的工作吗？

I was wondering if we can use a binary search tree to simulate heap operations (insert, find minimum, delete minimum), i.e., use a BST for doing the same job?

有什么样的好处，这样做？

Are there any kind of benefits for doing so?

推荐答案

当然，我们可以。但有一个平衡BST。

Sure we can. but with a balanced BST.

最小的是最左边的元素。最大是右端元件。找到这些元素是 O（LOGN）每一个，并且可以在每个插入缓存/删除，数据结构被修改后的[注有空间的优化在这里，但是这天真的做法也并不矛盾复杂性的要求！]

The minimum is the leftest element. The maximum is the rightest element. finding those elements is O(logn) each, and can be cached on each insert/delete, after the data structure was modified [note there is room for optimizations here, but this naive approach also doesn't contradict complexity requirement!]

这样你得到的插入，删除： O（LOGN），findMin / findMax： O（1）

This way you get insert,delete: O(logn), findMin/findMax: O(1)

编辑：
我能想到的在这个implementtion唯一的好处是，你在一个数据结构中同时获得findMin，findMax。
然而，这种解决方案将是慢得多[每步多个op，更高速缓存未命中，预计...]和消耗更多的空间，然后经常基于数组的实现一个堆

The only advantage I can think of in this implementtion is that you get both findMin,findMax in one data structure.
However, this solution will be much slower [more ops per step, more cache misses are expected...] and consume more space then the regular array-based implementation of a heap.

这篇关于我们可以用二叉搜索树模拟堆操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！