Пусть в двоичную кучу добавили элементов. Докажите, что в такой куче найдется не более, чем вершин с высотой (высота - это расстояние от вершины до самого глубокого листа в поддереве этой вершины).

Рассмотрим двоичную кучу, которая является почти полным двоичным деревом. Будем доказывать утверждение индукцией по h.

База индукции (h = 0). Вершины с высотой 0 – это листья кучи. Известно, что в любом двоичном дереве количество листьев не превосходит ⌈n/2⌉ (поскольку у каждого внутреннего узла может быть не более двух детей, а почти полное дерево обладает свойством: почти половина вершин – листья). Следовательно, утверждение выполняется для h =
0.

Переходный шаг. Пусть для некоторого h ≥ 0 доказано, что количество вершин с высотой h не более ⌈n/2^(h+1)⌉. Те...