индекс 3-го наименьшего элемента в макс куче

Question

Как найти возможные индексы 3-го наименьшего элемента в макс куче от 1 до n отдельных элементов? Я знаю, что самый маленький элемент будет в любом месте листа. второй самый маленький будет от n/2 до n для n больше, чем 3 Но я не знаю, чтобы рассчитать для 3-го наименьшего. Какие-либо предложения?

Answer 1

Третий-самый маленький элемент имеет не более двух потомков, а это означает, что его ребенок (ren) является листом или листом. (Чтобы доказать это, вам также нужно доказать, что для элемента с одним ребенком невозможно иметь нелистный лист. Легкий, но утомительный.)

Листья, как вы почти замечаете, имеют индексы в диапазон [floor(n/2)+1, n]. Если n/2 является целым числом, то этот элемент имеет ровно один дочерний элемент (который является листом), поэтому добавление дает диапазон индексов, который может содержать второй по величине элемент.

Элемент, у которого первый ребенок находится в диапазоне листьев [floor(n/2)+1,n], имеет не более двух детей, и нет нелистового ребенка. Этот диапазон смежна с диапазоном [ceil (n/2), n], и объединение двух диапазонов обеспечивает все возможные положения для третьего по величине элемента.

Первый дочерний элемент в i имеет индекс 2i, поэтому первый элемент, первый ребенок, по крайней мере floor(n/2)+1 является floor(n/4)+1.

Таким образом, возможные индексы, в которых вы можете найти третий по величине элемент, - это диапазон: [floor(n/4)+1,n].

---

Вот еще один подход. Возьмите некоторый элемент по индексу i. Его непосредственными детьми являются 2i и 2i+1; его внуками являются 4i, 4i+1, 4i+2, 4i+3 и, в общем, его потомки на уровне k являются 2ki, 2ki+1, ..., 2ki + 2ki-1; в сумме, [2ki, ..., 2k(i+1)-1 ]. Эти диапазоны, конечно, не перекрываются (действительно, если i не является 1, они даже не смежны). Так что если i имеет по крайней мере одного потомка на уровне k, он также имеет полный набор потомков для всех k' < k, из которых 2k-2.

Из всего этого можно сделать вывод:

• Если n ≥ 2ki and n < 2k(i+1), то i имеет:

  • 2ki-2 потомков на каком-то уровне менее k

  • n - 2ki+1 потомков на уровне k ;

  • Всего: n-1 Потомки.

• Если n ≥ 2k(i+1) and n < 2k+1i, то i имеет:

  • точно 2k+1-1 потомки.

Грубо говоря, это означает, что последние 2k элементы не найдены в первой 1/2k части основного массива кучного в.