查找存储为Ahnentafel数组的二进制最大堆的最小元素 [英] Finding the smallest element of a binary max heap stored as Ahnentafel array

问题描述

我有一个二进制最大堆（最高的元素在顶部），我需要保持它的常量大小（如20个元素），通过摆脱最小的元素，每次我到达20个元素。二进制堆存储在数组中，节点i的子节点为2 * i和2 * i + 1（i为0）。在任何时候，堆都有0到20之间的'n_elements'元素。例如，数组[16,14,10,8,7,9,3,2,4]将是一个有效的最大二进制堆， 16有孩子14和10，14有孩子8和7 ...

要找到最小的元素，似乎通常我必须从n_elements遍历数组/ 2到n_elements：最小的元素不一定是数组中的最后一个元素。

所以，只有这个数组，似乎尝试找到/删除最小的elt至少是O（n）。这是正确的吗？

解决方案

没有任何方法我可以想到，你可以更好地 O（n）通过单独使用堆来查找和删除最大堆中的最小元素的性能。您可以采取的一种方法是：

如果您自己创建此堆数据结构，则可以单独指向数组中最小元素的位置。所以每当一个新的元素添加到堆时，检查新的元素是否更小。如果是，请更新指针等。然后找到最小的元素将为 O（1）。

MBo在评论中提出了一个很好的一点，即每次删除后如何获取下一个最小的元素。在删除后，您仍然需要执行O（n）的操作来找到下一个最小的元素。所以删除仍然是 O（n）。但是找到最小的元素将是 O（1）

如果你需要更快的删除，你会还需要保持所有元素的最小堆。在这种情况下，删除将是 O（log（n））。插入将需要2倍的时间，因为你必须插入两个堆，它也将需要2x空间。

顺便说一下，如果你在任何时候只有20个元素时间，这不是真的太重要了（除非是作业问题，否则你只是为了乐趣而做）。只有当您计划将其扩展到数千个价值观时，这真的很重要。

I have a binary max heap (largest element at the top), and I need to keep it of constant size (say 20 elements) by getting rid of the smallest element each time I get to 20 elements. The binary heap is stored in an array, with children of node i at 2*i and 2*i+1 (i is zero based). At any point, the heap has 'n_elements' elements, between 0 and 20. For example, the array [16,14,10,8,7,9,3,2,4] would be a valid max binary heap, with 16 having children 14 and 10, 14 having children 8 and 7 ...

To find the smallest element, it seems that in general I have to traverse the array from n_elements/2 to n_elements: the smallest element is not necessarily the last one in the array.

So, with only that array, it seems any attempt at finding/removing the smallest elt is at least O(n). Is that correct?

解决方案

There isn't any way I can think of by which you can get better that O(n) performance for finding and removing the smallest element from a max heap by using the heap alone. One approach that you can take is:

If you are creating this heap data structure yourself, you can keep a separate pointer to the location of the smallest element in the array. So whenever a new element is added to the heap, check if the new element is smaller. If yes, update the pointer etc. Then finding the smallest element would be O(1).

MBo raises a good point in the comment about how to get the next smallest element after each removal. You'll still need to do the O(n) thing to find the next smallest element after each removal. So removal would still be O(n). But finding the smallest element would be O(1)

If you need faster removal as well, you'll need to also maintain a min-heap of all the elements. In that case, removal would be O(log(n)). Insertion will take 2x time because you have to insert into two heaps and it will also take 2x space.

By the way, if you have only 20 elements at any point of time, this is not really going to matter much (unless it is a homework problem or you are just doing it for fun). It would really matter only if you plan to scale it to thousands of values.

这篇关于查找存储为Ahnentafel数组的二进制最大堆的最小元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！