Binary Heap məlumat strukturu

[codex]

Binary Heap nədir?

Binary Heap, xüsusi ikili ağac (binary tree) əsaslı məlumat strukturu olub, yığın (heap) xüsusiyyətini təmin edir.

Bu struktura görə, hər bir “x” düyünü öz valideyni “p” ilə əlaqəlidir və:

• Max Heap-də valideynin dəyəri hər zaman uşaqlarından böyükdür.
• Min Heap-də valideynin dəyəri hər zaman uşaqlarından kiçikdir.

Binary Heap-in istifadə sahələri

Binary Heap, prioritet növbələri (priority queues) yaratmaq üçün geniş istifadə edilir. Bu strukturlar:
Heap Sort (yığın çeşidləmə) alqoritmində,
Dijkstra və digər qraf alqoritmlərində,
Maksimum və minimum dəyərin sürətli çıxarılması üçün istifadə olunur.

Binary Heap növləri

1. Max Heap:

   • Hər bir valideyn düyünün dəyəri uşaqlarından böyükdür.
   • Ən böyük element həmişə kökdə olur.

2. Min Heap:

   • Hər bir valideyn düyünün dəyəri uşaqlarından kiçikdir.
   • Ən kiçik element həmişə kökdə olur.

---

Max Binary Heap-in qaydaları

1. Hər valideyn maksimum iki uşaq düyünə sahib ola bilər.
2. Valideynin dəyəri uşaqlarından böyükdür.
3. Qardaş düyünlər arasında heç bir dəyər qaydası yoxdur.
4. Yığın mümkün qədər sıx yerləşdirilir – sol tərəf həmişə ilk doldurulur.

---

Binary Heap-in JavaScript-də implementasiyası

Binary Heap classın yaradılması

Əsas classı yaradıb, values adlı boş array içində saxlayırıq.

class BinaryHeap {
  constructor() {
    this.values = [];
  }
}

---

Element əlavə etmə (Insert)

Yeni element daxil etmək üçün insert() metodunu qururuq.

İş prinsipi:

1. Yeni element values array-ə push olunur.
2. Yeni əlavə edilən element “Bubble Up” alqoritmi ilə doğru mövqeyə yerləşdirilir:
   • Yeni elementin indeksi (index) təyin edilir.
   • Valideynin indeksi (parentIndex) hesablanır:
     $$ \text{parentIndex} = \lfloor \frac{index-1}{2} \rfloor $$
   • Valideyn daha kiçikdirsə, yerləri dəyişdirilir (swap edilir) və proses təkrarlanır.

Kod:

insert(element){
  this.values.push(element);
  
  let idx = this.values.length - 1;
  const el = this.values[idx];
  
  while(idx > 0) {
    let parentIdx = Math.floor((idx - 1) / 2);
    let parent = this.values[parentIdx];
    if(el <= parent) break;

    this.values[parentIdx] = el;
    this.values[idx] = parent;
    idx = parentIdx;
  }
}

---

Element silmə (ExtractMax)

Ən böyük elementi (Max Heap-də) silmək üçün extractMax() metodu yaradılır.

İş Prinsipi:

1. İlk element (ən böyük dəyər) ilə sonuncu element swap edilir.
2. Sonuncu element array-dən silinir (pop edilir).
3. Yeni kök elementi “Sink Down” metodu ilə düzgün mövqeyə yerləşdirilir:
   • Sol və sağ uşaqların indeksləri təyin edilir:
     • leftChildIdx = 2 * index + 1
     • rightChildIdx = 2 * index + 2
   • Əgər hər iki uşaq daha böyükdürsə, ən böyüyü ilə swap edilir.
   • Proses uşaqlardan biri daha böyük olana qədər təkrarlanır.

Kod:

extractMax() {
  const max = this.values[0];
  const end = this.values.pop();

  if (this.values.length > 0) {
    this.values[0] = end;
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];

    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
          swap = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;

      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }

  return max;
}

---

Prioritet növbələri (Priority Queue)

Prioritet növbəsi, elementlərin önəmlilik səviyyəsinə görə sıralandığı məlumat strukturudur.

İş prinsipi:

• Kiçik dəyər daha yüksək prioritet deməkdir.
• Enqueue (Daxil Etmə): Yeni düyün priority-ə görə yerləşdirilir.
• Dequeue (Sil və Qaytar): Kök elementi çıxarır və yığını yenidən tənzimləyir.

---

Prioritet növbəsinin JavaScript-də implementasiyası

class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element.priority >= parent.priority) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }
}

Node classı:

class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
  }
}

İstifadə nümunəsi:

let ER = new PriorityQueue();
ER.enqueue("common cold", 5);
ER.enqueue("gunshot wound", 1);
ER.enqueue("high fever", 4);
ER.enqueue("broken arm", 2);
ER.enqueue("glass in foot", 3);
ER.enqueue("grenade wound", 1);

console.log(ER);
console.log("***************");
console.log(ER.dequeue());

---

Nəticə

Binary Heap, Max Heap və Min Heap olaraq iki növə ayrılır.
Prioritet növbələri Binary Heap üzərində qurula bilər.
Heap əsaslı alqoritmlər qraf alqoritmlərində və çeşidləmədə geniş istifadə olunur.