Самый большой предмет в куче

Question

Самый большой элемент в куче должен появиться в позиции 1, а второй по величине должен быть в позиции 2 или позиции 3. Дайте список позиций в куче размером 31, где k-й по величине (i) может появиться, и (ii) не может появиться, для k = 2, 3, 4 (при условии, что значения быть отчетливым).

Я пытаюсь изучить это для своего среднесрочного периода, но сейчас уже 3 часа ночи, и я застрял в этой проблеме в книге, поскольку она не дает решения. Любая помощь будет оценена.

Answer 1

Если вы посмотрите на пример Реализация кучи в Википедии, вы увидите, что третье по величине может быть в позиции 2 или 3, в зависимости от того, что второе по величине нет, а также позиции 4 + 5 или 6 + 7, в зависимости от того, где находится второй по величине. Таким образом, это может быть в 2-7.

Четвертый по величине должен находиться в любой позиции, где может быть третий по величине, плюс любая позиция, которая является прямым потомком третьего по величине Это означает, что это может быть где-то от 2-15.

На следующем рисунке показано 0, так как это реализация массива, поэтому добавьте один для позиции.