h3(#stergere). Ştergere

Operaţia de ştergere este inversul operaţiei de inserare. (Se va desena o figură) Dacă dorim să suprimăm nodul $z$, atunci cât timp $z$ nu este o frunză, alegem fiul $w$ cu prioritatea mai mare şi facem o rotaţie pentru a aduce pe $w$ în locul lui $z$. Astfel, după cum este explicat la '$rotaţii$':treapuri#rotatii, nivelul lui $z$ scade cu $1$ până când devine o frunză. La finalul algoritmului, după ştergerea lui $z$, arborele va redobândi structura de heap.

Operaţia de ştergere este inversul operaţiei de inserare. Să presupunem că dorim să ştergem un nod $z$. Pentru a înţelege mai uşor, îi vom atribui prioritatea $0$, prioritatea cea mai mică. În continuare îi vom aplica treapului $T$ al doilea tip de rotaţii pentru ca să redobândească proprietatea de heap. Este evident că, la sfârşitul algoritmului, $z$ va fi o frunză şi nu ne rămâne decât să îl ştergem.

Complexitate: $O(log N)$.