permheap

Permheap

== include(page="template/taskheader" task_id="permheap") ==

Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile afociate fiecăruia dintre fii săi. Astfel, putem reprezenta un heap printr-un vector în care elementele sunt memorate începând cu poziţia $1$ iar fiii nodului de pe poziţia $i$ sunt nodurile de pe poziţiile $2*i$ şi $2*i+1$. Toate nivelurile arborelui sunt complete (fiecare nod are exact $2$ fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga.

Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile asociate fiecăruia dintre fii săi. Astfel, putem reprezenta un heap printr-un vector în care elementele sunt memorate începând cu poziţia $1$ iar fiii nodului de pe poziţia $i$ sunt nodurile de pe poziţiile $2*i$ şi $2*i+1$ (nodurile de pe acelaşi nivel ni le imaginăm aşezate de la stânga la dreapta, în ordine crescătoare a poziţiilor lor). Toate nivelurile arborelui sunt complete (fiecare nod are exact $2$ fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga (adică întâi frunzele de pe poziţii mai mici).

Să se determine câte permutări ale mulţimii ${1, 2, ... n}$ au structură de heap.