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

Третий наименьший элемент имеет не более двух потомков, что означает, что его дочерний элемент (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 часть базового массива кучи.