找到最大堆中第k个最大元素的位置 [英] Find the position of the k-largest element in max-heap

问题描述

在这里做一些算法作业:(

Doing some algorithms homework here :(

我需要提出一个方程来找到max-heap数组中所有可能的位置，给定第k个元素可能在其中.

I need to come up with an equation to find all the possible positions in the max-heap array, where a given k-th element might be.

i.e. the largest element (k=1) is at position n=1.
The second largest element (k=2) can be at positions n=2\3.
Element k=3 can also be in positions n=2\3.
...
The 6th largest element (k=6) can be in positions n=4 up to n=7.
etc.

并没有真正提出可靠的计算.

Didn't really come up with a solid calculation.

任何输入将不胜感激.

推荐答案

第六大元素可以更远.极端的情况是，前六个元素是根和一系列正确的子元素.每个子节点位于节点2n+1上，其中n是父节点.最右边的序列的索引序列是1、3、7、15、31、63(也称为2 ^ 6-1).其他较小的值则填充在每个分支的左侧.

The 6th-largest element can be much farther out. The extreme case is where the first six elements are the root and a series of right-children. Each child is at node 2n+1, where n is the parent's node. The sequence of indices for the right-most sequence is 1, 3, 7, 15, 31, 63 (a.k.a. 2^6-1). Other, smaller values fill in the left side of each branch.

最早的位置是如果相同的值恰好是根的左孩子，而所有其他值都到达了右分支:它出现在位置2.再次，根据需要出现较小的值.

The earliest position is if that same value happened to be the left-child of the root, while all of the others went to the right branch: it appears in location 2. Again, smaller values appear as needed.

因此，可能值的范围为2到2 ^ n-1. 您剩下的问题是确定哪些剩余位置可以包含该第六大元素.

So, the range of possible values is from 2 to 2^n-1. Your remaining problem is to determine which of the remaining locations can contain that 6th-largest element.

绘制一棵适当深度的树-更好的是，仅将其深4层，并使用第4大元素.假设使用99、98、98、96，然后其他"值可以是1到11.在树的任何位置上，您都可以放置96您不能 排列其他数字形成法律树?

Draw a tree of the proper depth -- better yet, do this only 4 levels deep, and work with the 4th-largest element. Say, use 99, 98, 98, 96, and then the "other" values can be 1 through 11. Is there anywhere on this tree you can put 96 that you cannot arrange the other numbers to form a legal tree?

再将树扩展一级. 现在哪里是您不能放置96的孔?

Expand the tree one more level. Now where are the holes in which you cannot put 96?

这会让您放松吗?

这篇关于找到最大堆中第k个最大元素的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！