Implementing a Reactive Priority Queue in Vue.js (TypeScript)

This challenge focuses on building a fundamental data structure, a priority queue, within a Vue.js application using TypeScript. A priority queue is essential for scenarios where elements need to be processed based on their priority, not just the order they were added. You'll create a reusable Vue component that allows users to add items with associated priorities and then retrieve the highest priority item.

Problem Description

Your task is to create a Vue.js component that encapsulates a priority queue. This component should allow users to:

1. Add items: Users should be able to add new items to the queue. Each item will have a value (any data type) and a priority (a number, where lower numbers indicate higher priority).
2. Retrieve highest priority item: Users should be able to dequeue the item with the highest priority from the queue.
3. Observe queue state: The component should be reactive, meaning that any changes to the queue (adding or removing items) should be reflected in the UI if bound to it.

Key Requirements:

• TypeScript: The entire implementation must be in TypeScript.
• Vue Component: Create a functional or options API Vue component.
• Priority Queue Logic: Implement the core priority queue logic. You can choose your preferred underlying implementation (e.g., a sorted array, a binary heap), but it must correctly maintain priority order.
• Reactivity: Ensure that when items are added or removed, any Vue bindings to the queue's state update accordingly.
• Clear API: Provide a simple and intuitive API for interacting with the priority queue component from its parent.

Expected Behavior:

• When an item with a higher priority (lower number) is added, it should be placed before lower priority items.
• Dequeuing should always return the item with the smallest priority number.
• If multiple items have the same highest priority, any one of them can be returned.

Edge Cases to Consider:

• Empty Queue: What happens when dequeue is called on an empty queue?
• Duplicate Priorities: How are items with identical priorities handled?
• Non-numeric Priorities: While the problem specifies numbers, consider how you might handle or validate non-numeric inputs for priority (though strict numeric input is acceptable for this challenge).

Examples

Example 1: Basic Usage

// Parent Component (Conceptual)
<template>
  <div>
    <PriorityQueue @item-added="handleItemAdded" @item-dequeued="handleItemDequeued">
      <button @click="addItem('Task A', 2)">Add Task A (Priority 2)</button>
      <button @click="addItem('Task B', 1)">Add Task B (Priority 1)</button>
      <button @click="addItem('Task C', 3)">Add Task C (Priority 3)</button>
      <button @click="dequeueItem">Dequeue Highest Priority</button>
    </PriorityQueue>
    <p>Queue State: {{ queueItems }}</p>
    <p>Dequeued Item: {{ lastDequeuedItem }}</p>
  </div>
</template>

<script lang="ts">
import { defineComponent, ref } from 'vue';
import PriorityQueue from './components/PriorityQueue.vue'; // Assuming you create this component

export default defineComponent({
  components: {
    PriorityQueue,
  },
  setup() {
    const queueItems = ref<any[]>([]); // To display queue state for debugging/visualization
    const lastDequeuedItem = ref<any>(null);

    const handleItemAdded = (items: any[]) => {
      queueItems.value = items;
    };

    const handleItemDequeued = (item: any) => {
      lastDequeuedItem.value = item;
      // You might also want to update queueItems.value here if the component doesn't emit the full updated list
    };

    return {
      queueItems,
      lastDequeuedItem,
      handleItemAdded,
      handleItemDequeued,
      // Methods to interact with the PriorityQueue component
      addItem: (value: any, priority: number) => {
        // Assume PriorityQueue component has an 'add' method
        // This part would depend on how you expose the PriorityQueue's methods
        console.log(`Attempting to add: ${value} with priority ${priority}`);
      },
      dequeueItem: () => {
        // Assume PriorityQueue component has a 'dequeue' method
        console.log('Attempting to dequeue');
      },
    };
  },
});
</script>

Output (after clicking buttons in order: Add Task A, Add Task B, Add Task C, Dequeue Highest Priority):

• Console Logs:
  • Attempting to add: Task A with priority 2
  • Attempting to add: Task B with priority 1
  • Attempting to add: Task C with priority 3
  • Attempting to dequeue
• queueItems.value (after all adds): [{ value: 'Task B', priority: 1 }, { value: 'Task A', priority: 2 }, { value: 'Task C', priority: 3 }] (order might vary slightly based on internal implementation for equal priorities, but 'Task B' should be first).
• lastDequeuedItem.value (after dequeue): { value: 'Task B', priority: 1 }
• queueItems.value (after dequeue): [{ value: 'Task A', priority: 2 }, { value: 'Task C', priority: 3 }]

Example 2: Handling Empty Queue

// Parent Component (Conceptual) - continuing from Example 1
<template>
  <div>
    <PriorityQueue @item-added="handleItemAdded" @item-dequeued="handleItemDequeued">
      <button @click="dequeueItem">Dequeue Highest Priority</button>
    </PriorityQueue>
    <p>Queue State: {{ queueItems }}</p>
    <p>Dequeued Item: {{ lastDequeuedItem }}</p>
    <p>Queue Empty Message: {{ emptyMessage }}</p>
  </div>
</template>

<script lang="ts">
// ... (previous script setup)
import { ref } from 'vue'; // Import ref if not already

export default defineComponent({
  // ... components and other setup
  setup() {
    // ... existing refs and methods

    const emptyMessage = ref<string>('');

    const handleItemDequeued = (item: any) => {
      if (item === null) { // Assuming dequeue on empty returns null or undefined
        emptyMessage.value = 'Queue is empty!';
        lastDequeuedItem.value = null;
      } else {
        lastDequeuedItem.value = item;
        emptyMessage.value = '';
      }
    };

    return {
      // ... existing return values
      emptyMessage,
      handleItemDequeued,
      // ... existing addItem and dequeueItem methods
    };
  },
});
</script>

Output (after clicking "Dequeue Highest Priority" on an empty queue):

• queueItems.value: []
• lastDequeuedItem.value: null (or undefined)
• emptyMessage.value: "Queue is empty!"

Constraints

• Priority Values: Priority values will be integers.
• Item Values: Item values can be of any JavaScript type (string, number, object, etc.).
• Queue Size: The queue can theoretically hold an unlimited number of items.
• Performance: For typical use cases (up to thousands of items), adding and removing items should ideally be efficient (e.g., O(log n) or O(n) depending on implementation choice).

Notes

• Consider how you will expose the add and dequeue methods from your PriorityQueue component to its parent. Using defineExpose in the Composition API or exposing methods on the component instance in the Options API are common approaches.
• You'll likely need to emit events from the PriorityQueue component to inform the parent about changes (e.g., item-added, item-dequeued) so the parent can update its own state or UI.
• Think about the structure of the items in the queue. A simple object like { value: T, priority: number } is recommended.
• A sorted array implementation is simpler but less performant for large queues (O(n) for add). A binary heap implementation offers better performance (O(log n) for both add and remove) but is more complex to implement. Choose what best suits your understanding and time.
• Vue's reactivity system will automatically handle updating the UI if you expose and manage the queue's state correctly within the component.