জাভাস্ক্রিপ্টে PriorityQueue-এ Enqueue (Add) অপারেশন

PriorityQueue: Enqueue Operation (প্রায়োরিটির সাথে এলিমেন্ট যোগ করা)

Enqueue মানে প্রায়োরিটি কিউর সঠিক পজিশনে এলিমেন্ট যোগ করা যাতে প্রায়োরিটি অনুযায়ী সর্টেড অর্ডার মেনটেইন থাকে। আমরা Insertion Sort-এর মতো লজিক ব্যবহার করি।

Enqueue মেথড ইমপ্লিমেন্টেশন

class PriorityQueue {
  constructor(maxSize = 10) {
    this.maxSize = maxSize;
    this.container = [];
  }

  isFull() {
    return this.container.length >= this.maxSize;
  }

  // Enqueue Implementation
  enqueue(data, priority) {
    // Overflow চেক
    if (this.isFull()) {
      console.log("Queue Overflow! কিউর সর্বোচ্চ সাইজে পৌঁছেছে।");
      return false;
    }

    // নতুন এলিমেন্ট অবজেক্ট তৈরি
    const newElement = new PriorityQueue.Element(data, priority);
    let added = false;

    // লিনিয়ার সার্চ করে সঠিক পজিশন খুঁজুন
    // Higher Priority = Higher Number (Convention)
    for (let i = 0; i < this.container.length; i++) {
      if (newElement.priority > this.container[i].priority) {
        // নতুন এলিমেন্টের প্রায়োরিটি বেশি -> এখানে ইনসার্ট
        this.container.splice(i, 0, newElement);
        added = true;
        break;
      }
    }

    // যদি সবচেয়ে কম প্রায়োরিটি হয় -> শেষে পুশ
    if (!added) {
      this.container.push(newElement);
    }
    return true;
  }

  // ... dequeue, peek, clear, display ...
}

// Inner Element Class
PriorityQueue.Element = class {
  constructor(data, priority) {
    this.data = data;
    this.priority = priority;
  }
};

টেস্টিং উদাহরণ

const pq = new PriorityQueue(5);

pq.enqueue("Hello", 3);
pq.enqueue("World", 2);
pq.enqueue("Foo", 8);

pq.display();
// আউটপুট:
// [
//   { data: 'World', priority: 2 },   // Lowest priority
//   { data: 'Hello', priority: 3 },
//   { data: 'Foo', priority: 8 }      // Highest priority (Tail)
// ]

// আরেকটি টেস্ট: মাঝপথে ইনসার্ট
pq.enqueue("Bar", 5); // Priority 5 -> Hello(3) এবং Foo(8) এর মাঝপথে
pq.display();
// [
//   { data: 'World', priority: 2 },
//   { data: 'Hello', priority: 3 },
//   { data: 'Bar', priority: 5 },    // Inserted here
//   { data: 'Foo', priority: 8 }
// ]

Insertion Sort Analogy

Enqueue অপারেশন Insertion Sort-এর ইনসারশন স্টেপের মতো কাজ করে:

• অ্যারে ইতিমধ্যে সর্টেড (প্রায়োরিটি অনুযায়ী)।
• নতুন এলিমেন্টের জন্য সঠিক পজিশন খুঁজে splice() দিয়ে ইনসার্ট।
• ফলাফল: অ্যারে সবসময় সর্টেড থাকে।

Priority Convention: Higher Number = Higher Priority

এই ইমপ্লিমেন্টেশনে বড় সংখ্যা = উচ্চ প্রায়োরিটি। আপনি চাইলে উল্টা করতে পারেন:

// Lower Number = Higher Priority (যেমন: 1 = Critical, 10 = Low)
if (newElement.priority < this.container[i].priority) {
  this.container.splice(i, 0, newElement);
  // ...
}

সিদ্ধান্ত নিন এবং কনসিস্টেন্ট থাকুন।

Time Complexity

• Best Case: O(1) — নতুন এলিমেন্ট সবচেয়ে কম প্রায়োরিটি (শেষে পুশ)।
• Worst Case: O(n) — নতুন এলিমেন্ট সবচেয়ে বেশি প্রায়োরিটি (শুরুতে ইনসার্ট, সব শিফট)۔
• Average: O(n) — লিনিয়ার সার্চ।

Optimization: Binary Search for Insert Position

enqueue(data, priority) {
  if (this.isFull()) return false;
  
  const newElement = new PriorityQueue.Element(data, priority);
  
  // Binary Search for Insert Index (O(log n))
  let low = 0, high = this.container.length;
  while (low < high) {
    const mid = (low + high) >>> 1;
    if (this.container[mid].priority < newElement.priority) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  // low = insert position
  this.container.splice(low, 0, newElement);
  return true;
}

এটি সার্চকে O(log n)-এ নামিয়ে আনে, কিন্তু splice O(n) থাকে (শিফটিং)। মোট O(n)ই, কিন্তু কনস্ট্যান্ট ফ্যাক্টর কম।