Двоичная куча: доказательство сложности построения О(n)

[EuroElessar]

Я все понимаю, но данный вопрос и так прекрасно разобран в «Алгоритмы: построение и анализ» с более простым и коротким доказательством.

[SergeyBankevich]

Мда, программа не программа, доказательство не доказательство.

[spiff]

Еще я бы добавил ссылку к первоисточнику. Данный алгоритм был придуман Робертом Флойдом в 1964 году, как часть алгоритма TreeSort: Floyd, Robert W., (1964), Algorithm 245 — Treesort 3, Communications of the ACM 7 (12): 701