Structura de date de tip heap

Definiția și proprietățile

Ansamblul heap este un arbore binar cu două însușiri:

• arborele este aproape complet, adică are toate nivelurile complete, în afară de ultimul, care se completează de la stânga spre dreapta;
• cheile fiecărui părinte și ale fiilor lui respectă o relație de ordine prestabilită.

Structura poartă și numele de arbore de selecție sau de arbore parțial ordonat. Relația de ordine aleasă dă două feluri de ansambluri:

• la heap-ul maxim, fiecare fiu are cheia cel mult egală cu a părintelui;
• la heap-ul minim, fiecare fiu are cheia cel puțin egală cu a părintelui.

Din definiție decurg următoarele proprietăți:

• Relația de ordine se transmite de-a lungul fiecărui drum spre frunze. La un heap maxim, niciun nod dintr-un subarbore nu depășește deci cheia rădăcinii acelui subarbore, iar rădăcina întregului arbore păstrează cheia cea mai mare. La heap-ul minim, ea păstrează cheia cea mai mică.
• Cheile se pot repeta.
• Frații nu se compară între ei, fiindcă relația de ordine îi leagă numai pe părinte și pe fiii lui. De aici vine numele de arbore parțial ordonat.
• Un ansamblu cu n noduri are înălțimea [log₂n], ca orice arbore aproape complet.
• Pe extragerea repetată a rădăcinii se bazează coada cu priorități: cheile ies din structură în ordinea dată de relația de ordine prestabilită. De aici vine numele de arbore de selecție.

Reprezentarea în memorie

i   1  2  3  4  5  6  7  8  9 10
v  50 30 40 25 20 35 15 10 22 18

Inserarea unei chei

Descrierea etapelor. Prin inserare, arborele trebuie să rămână ansamblu heap, deci trebuie să rămână arbore aproape complet și să păstreze relația de ordine între părinte și fii.

1. Se verifică dacă mai există loc în vector, adică dacă lungimea logică n este mai mică decât lungimea fizică.
2. Nodul nou își găsește locul pe ultimul nivel, în prima poziție liberă din dreapta nodurilor existente. Când ultimul nivel s-a umplut, el deschide nivelul următor, în extremitatea stângă. În vector, aceasta înseamnă că n crește cu 1, iar cheia se scrie în v[n].
3. După adăugare, cheia nouă poate să nu respecte relația de ordine cu părintele ei, deci se propagă spre rădăcină: nodul nou devine nod curent, iar cheia lui se compară cu cheia părintelui.
4. Cât timp nodul curent nu este rădăcina și cheia lui o depășește pe cea a părintelui, cele două chei se interschimbă, iar părintele devine nod curent.
5. Propagarea se oprește când relația de ordine este respectată sau când nodul curent a ajuns rădăcina.

Exemplificarea etapelor. În ansamblul de mai sus se inserează cheia 45.

Cheia 45 a urcat două niveluri, prin două interschimbări, iar arborele are acum 11 noduri.

Eliminarea nodului cu cheia maximă

Descrierea etapelor. Într-un heap maxim, cheia cea mai mare se află în rădăcină, deci eliminarea nodului cu cheia maximă înseamnă eliminarea rădăcinii. Și după această operație arborele trebuie să rămână aproape complet și să păstreze relația de ordine.

1. Se reține cheia din rădăcină, v[1], fiindcă ea este rezultatul operației.
2. Pentru ca arborele să rămână aproape complet, din el trebuie să dispară ultimul nod de pe ultimul nivel, nu rădăcina. De aceea cheia ultimului nod se aduce în rădăcină, iar n scade cu 1.
3. Cheia adusă în rădăcină poate să nu fie în relația de ordine cu fiii ei, deci se propagă spre nivelurile inferioare: rădăcina devine nod curent.
4. Cât timp nodul curent are cel puțin un fiu, se alege fiul cu cheia mai mare. Dacă această cheie este mai mare decât cheia nodului curent, cele două chei se interschimbă, iar fiul devine nod curent.
5. Propagarea se oprește când cheia nodului curent este mai mare sau egală cu cheile fiilor lui sau când nodul curent nu mai are fii.

Exemplificarea etapelor. Se elimină nodul cu cheia maximă din ansamblul cu 11 noduri obținut mai sus: 50, 45, 40, 25, 30, 35, 15, 10, 22, 18, 20.

Operația furnizează cheia 50, iar arborele rămas are 10 noduri și este tot heap maxim, cu cheia cea mai mare, 45, în rădăcină.

Problema propusă

Enunț. Se citesc de la tastatură un număr natural m (m ≤ 100), apoi m numere naturale, reprezentând punctajele obținute de concurenții unui concurs, și un număr natural k (k ≤ m). Se cere să se afișeze cele mai mari k punctaje, în ordine descrescătoare, separate prin câte un spațiu.

Exemplu: pentru m = 8, punctajele 12, 45, 7, 45, 30, 3, 28, 19 și k = 3 se afișează 45 45 30.

Descrierea soluției în limbaj natural. Punctajele se introduc, pe măsură ce sunt citite, într-un heap maxim, prin operația de inserare. La sfârșitul citirii, în rădăcina ansamblului se află cel mai mare punctaj.

Se aplică apoi de k ori operația de eliminare a nodului cu cheia maximă. Fiecare eliminare furnizează cel mai mare punctaj rămas și reface ansamblul, deci a doua eliminare furnizează al doilea punctaj ca mărime și așa mai departe. Punctajele astfel obținute se afișează în ordinea în care sunt extrase, care este chiar ordinea descrescătoare cerută.

Punctajele egale nu creează dificultăți, fiindcă într-un ansamblu heap pot exista chei egale: pe exemplul dat, valoarea 45 este extrasă de două ori.

Implementarea soluției.

#include <iostream>
using namespace std;

const int NMAX = 101;

int v[NMAX];   // heap-ul maxim; radacina este v[1]
int n = 0;     // numarul de noduri ale ansamblului

/* Insereaza cheia x: nodul nou se adauga dupa ultimul nod, iar cheia lui se
   propaga spre radacina cat timp este mai mare decat cheia parintelui. */
void inserare(int x) {
    n++;
    v[n] = x;
    int i = n;
    while (i > 1 && v[i] > v[i / 2]) {
        int aux = v[i];
        v[i] = v[i / 2];
        v[i / 2] = aux;
        i = i / 2;
    }
}

/* Elimina nodul radacina si furnizeaza cheia lui: in radacina se aduce cheia
   ultimului nod, care se propaga apoi spre nivelurile inferioare. */
int eliminaMaxim() {
    int x = v[1];
    v[1] = v[n];
    n--;
    int i = 1;
    while (2 * i <= n) {
        int j = 2 * i;                        // fiul stang
        if (j + 1 <= n && v[j + 1] > v[j])
            j++;                              // fiul cu cheia mai mare
        if (v[i] >= v[j])
            break;
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        i = j;
    }
    return x;
}

int main() {
    int m, k, x;

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x;
        inserare(x);
    }

    cin >> k;
    for (int i = 1; i <= k; i++)
        cout << eliminaMaxim() << " ";

    return 0;
}

Verificarea pe exemplul din enunț. După citirea celor opt punctaje, heap-ul maxim are în rădăcină valoarea 45. Prima eliminare furnizează 45, a doua furnizează al doilea 45, iar a treia furnizează 30. Se afișează 45 45 30.