在搜索的第7大元素的最大堆？ [英] Searching the 7th largest element in a max-heap?

问题描述

所以，我的朋友和我都没有看到眼对眼在这个问题上。它要求在最大堆n个元素的搜索的第7大元素的时间复杂度？

So my friend and I are not seeing eye to eye in this question. It asks for the time complexity of searching for the 7th largest element in a max-heap of n elements?

我认为它应该是O（n）和她是应该的意见是O（1）。我的逻辑是，假设n是7，然后第7大元素将在堆的最后一个元素，所以如果我们认为它应该是O（n）的最坏情况。然而，她说，因为它是一个最大堆所以找到第7大元素应该采取一定的时间。但用她的逻辑，即使是第50大元或100元最多可以在O（1）及时发现。 而且这本书中，我们遇到了这个问题，称该解决方案将是O（LOGN）。

I'm of the opinion that it should be O(n) and she is of the opinion it should be O(1). My logic is that suppose n is 7 then 7th largest element will be the last element in the heap so if we consider the worst case it should be O(n). She however says that since it's a max heap so finding the 7th largest element should take constant time. But using her logic even the 50th largest element or the 100th largest element can be found in O(1) time. Also the book in which we came across this question says the solution will be O(logn).

有人能告诉我哪种解决方案是正确的？

Can someone please tell me which solution is correct?

推荐答案

有一个O（1）解决方案。让我们假设堆重新psnted为一棵树$ P $和最大的元素是根。比与7个最大的元素和根的节点之间的距离小于或等于6的距离，以根＆所述节点的数量; = 6是从未大于1 + 2 + 4 + 8 + 16 + 32 + 64 = 127。它是一个常数。他们可以穿越在固定的时间。

There is an O(1) solution. Let's assume that the heap is represnted as a tree and max element is a root. Than the distance between the node with 7-th largest element and the root is less than or equal to 6. The number of nodes with distance to the root <= 6 is never greater than 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. It is a constant. They can traversed in constant time.

这篇关于在搜索的第7大元素的最大堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！