Նախապատվություններով հերթի իրականացումը

Հերթի այն տեսակը, որտեղ տարրերը կարող են ավելացվել կամայականորեն, բայց կարող են հեռացվել միայն ըստ նրանց մեջ սահմանված կարգի, կոչվում է նախապատվություններով հերթ։ Օրինակ, եթե որպես հերթի մեջ ավելացվող տարրեր դիտարկվում են թվերը, իսկ թվերի մեջ սահմանված կարգ է հանդիսանում "\(<\)" (փոքր է) գործողությունը, ապա ամեն անգամ հերթից որևէ տարր պահանջելով կստանանք այնտեղ եղած տարրերից ամենափոքրը (նույնը կարելի է ասել, իհարկե, "\(>\)" (մեծ է) գործողության նկատմամբ)։ Մեկ այլ օրինակում, եթե հերթի որպես տարրեր դիտարկվում են բառեր (տեքստ), իսկ որպես կարգի հարաբերությունը սահմանված է բառի երկարության նկատմամբ՝ \(|w_1| < |w_2|\), ապա ամեն անգամ հերթից տարր պահանջելով կստանանք այդ պահին հերթում մնացած ամենակարճ բառը։

Նախապատվություններով հերթն իրականացվում է մի տվյալների կառուցվածքի հիման վրա, որին գրականության մեջ տրված է heap (ռուս. куча) անունը։ Սա մի ծառ է (տվյալ դեպքում՝ բինար ծառ), որի ամեն մի հանգույցի արժեքն ավելի փոքր է (մեծ է) իր ժառանգների արժեքներից։ Բնականաբար ծառի արմատում գտնվում է ամենափոքր (կամ ամենամեծ) տարրը։ Այս ծառը նաև լրիվ (բինար) ծառ է։

Դասախոսությունների կամ այլ խոսակցությունների ժամանակ (քանի որ հայերեն գրականություն գործնականում չկա) ես հանդիպել եմ նաև heap տերմինի կույտ բառացի և, իմ կարծիքով, անհաջող թարգմանությանը։ Հանդիպել եմ նաև բուրգ տերմինը, և այս գրառման մեջ կօգտագործեմ հենց այս տարբերակը։

Ենթադրենք արդեն իրականացրել ենք Heap<T> շաբլոնային դասը որն ունի Add(T value) մեթոդը՝ հերթում տարրեր ավելացնելու համար, և T TakeMinimal() մեթոդը՝ հերթից ամենաբարձր նախապատվություն (տվյալ դեպքում՝ ամենափոքր արժեք) ունեցող տարրը հեռացնելու համար։ Ինչպես նաև նախատեսված է արժեքավորող ցուցակով կոնստրուկտոր։ Ստեղծենք int տիպի արժեքների հերթ և նրանում ավելացնենք {32, 9, 23, 14, 17, 2, 20, 17, 6} թվերը։

  Heap h {32, 9, 23, 14, 17, 2, 20, 17, 6};

Այս թվերով կառուցված ծառը կունենա ստորև բերված նկարի տեսքը, որում երևում է, որ ամեն մի հանգույցի արժեք ավելի փոքր է, քան իր ժառանգների արժեքները։ * * * Հիմա ներկայացնեմ իրականացումը։ Սովորաբար բուրգն իրականացվում է ոչ թե ցուցիչների վրա հիմնված դինամիկ կառուցվածքների միջոցով, այլ սովորական ինդեքսավորված վեկտորներով։ Բուրգի արմատի արժեքը գրվում է վեկտորի զրո ինդեքսով բջջում։ Իսկ ամեն մի k ինդեքսով հանգույցի աջ (R) ու ձախ (L) ժառանգների ինդեքսները հաշվվում են L=2k+1 և R=2k+2 բանաձևերով։ Օրինակ, նկարում բերված ծառը վեկտորի տեսքով կներկայանա հետևյալ կերպ.

 Value | 2 | 6 | 9 | 14| 17| 23| 20| 32| 17
-------+---+---+---+---+---+---+---+---+---
 Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

Այս ներկայացումն արդյունավետ է շնորհիվ այն բանի, որ բուրգը լրիվ ծառ է և ամենաներքևի մակարդակը լրացված է ձախից աջ։
Եվ այսպես, C++11 լեզվով սահմանում եմ Heap դասը։ Այս դասի size ստատիկ հաստատունը ցույց է տալիս տարրերի վեկտորի նախնական չափը։ capacity դաշտը ցույց է տալիս բուրգի տարողությունը, իսկ count դաշտը ցույց է տալիս տվյալ պահին առկա տարրերի քանակը։ Տարրերը պահվում են դինամիկ ստեղծվող data զանգվածում։

template
class Heap {
protected:
  static const int size = 32;

  unsigned int capacity;
  unsigned int count;
  T* data;

Դասի կոնստրուկտորներից մեկը պարզապես ստեղծում է դատարկ օբյեկտ, իսկ մյուսը բուրգի մեջ է ավելացնում արժեքավորող ցուցակով տրված տարրերը։ Իսկ դեստրուկտորը պարզապես ազատում է տարրերի զանգվածի զբաղեցրած հիշողությունը։

public:
  Heap()
    : capacity(size), count(0)
  {
    data = new T[capacity];
  }
  
  Heap( std::initializer_list<T> elems )
    : Heap()
  {
    for( auto e : elems )
      Add( e );
  }
    
  virtual ~Heap()
  {
    delete[] data;
  }

Նախապատվություններով հերթում նոր տարր ավելացնելիս նախ այն ավելացվում է զանգված վերջում, ապա, heapify գործողության կիրառմամբ զանգվածի տարրերը վերադասավորվում են այնպես, որ շարունակեն բավարարել բուրգի վերը նշված պահանջներին։ Եթե հերթական տարրն ավելացնելուց հետո պարզվում է, որ զանգվածի տեղերը սպառվել են (count == capacity), ապա զանգվածի երկարությունը կրկնապատկվում է։

  void Add( T val )
  {
    data[count] = val;
    ++count;
    heapify();
    if( count == capacity )
      enlarge();
  }

heapify գործողության ժամանակ տարրը տեղաշարժվում է դեպի ձախ այնքան ժամանակ, քանի դեռ այն փոքր է ծնոսի արժեքից։ Ի դեպ, տրված k ինդեքսով տարրի ծնողի ինդեքսը որոշվում է (k - 1)/2 բանաձևով։

  void heapify()
  {
    unsigned int i(count - 1);
    unsigned int k((i - 1) / 2);
    while( i > 0 && data[i] < data[k] ) {
      auto temp(data[i]);
      data[i] = data[k];
      data[k] = temp;
      i = k;
      k = (i - 1) / 2;
    }
  }

Զանգվածն ընդլայնող enlarge մեթոդը համակարգից պահանջում է գոյություն ունեցողից երկու անգամ մեծ հիշողություն, տարրերն արտագրում է այդ նոր տիրույթում և համակարգին է վերադարձնում հին տարածքը։

  void enlarge()
  {
    T* temp(data);
    capacity *= 2;
    data = new T[capacity];
    for( unsigned int i = 0; i < count; ++i )
      data[i] = temp[i];
    delete[] temp;
  }

Նախապատվություններով հերթից ամենաբարձր նախապատվություն ունեցող տարրը հեռացնելու համար գրված է TakeMinimal մեթոդը։ Այն հեռացնում է բուրգի գագաթի տարրը, ապա մյուս տարրերը վերադասավորում է այնպես, որ նրանք շարունակեն բավարարել բուրգի պայմաններին և վերադարձնում է հեռացված արժեքը։ Այս մեթոդում վերադասավորման համար օգտագործված է heapify մեթոդը։ Բայց գաղափարն այն է, որ ամենաներքևի մակարդակի ամենաաջ տարրը տեղափոխվում է բուրգի գագաթը, ապա այն փոխատեղվում է իր ժառանգներից ամենափոքրի հետ այնքան ժամանակ, քանի դեռ չի հասել իր իսկական տեղին։

  T TakeMinimal()
  {
    auto result(data[0]);
    data[0] = data[--count];
    heapify();
    if( count * 2 == capacity )
      reduce();
    return result;
  }

TakeMinimal մեթոդով որևէ տարր հեռացնելուց հետո ստգուգվում է տարրերի զանգվածի վիճակը։ Եթե զանգվածի տարողությունը երկու անգամ մեծ է տարրերի իրական քանակից՝ count * 2 == capacity, ապա զանգվածի չափը կրճատվում է երկու անգամ։ reduce մեթոդը ստեղծում է երկու անգամ փոքր տիրույթ, տարրերն արտագրում է նրա մեջ, ապա համակարգին է վերադարձնում ին մեծ տիրույթը։

  void reduce()
  {
    if( capacity > size ) {
      capacity /= 2;
      auto temp(data);
      data = new T[capacity];
      for( unsigned int i = 0; i < count; ++i )
        data[i] = temp[i];
      delete[] temp;
    }
  }
};

* * * Առայժմ այսքանը նախապատվություններով հերթերի մասին։ Չնայած որ տեքստը մի քիչ կցկտուր ստացվեց, բայց, կարծում եմ, որ ընդհանուր առմամբ այն հասկանալի է։