Precedence Queue is a flexible and environment friendly knowledge construction, that represents subtle and sensible method to knowledge processing. By design, components are managed not simply by the order of their arrival however in line with their precedence. This mechanism performs an essential function in optimizing duties in quite a few purposes, from algorithm design to system useful resource administration.
Whereas Precedence Queues could be carried out with numerous knowledge constructions like Arrays, Linked Lists, Heaps or Binary Timber – utilizing a Binary Heap is the most well-liked alternative and that is the implementation we might be specializing in by way of this text.
Binary Heaps, a typical implementation of Heaps, lay the groundwork for Precedence Queues. They arrive in two most important varieties: Max Heaps and Min Heaps. Max Heaps locations larger values to be processed first, whereas the Min Heaps does the alternative – lesser values are favored to be processed first. For Precedence Queues, though each varieties are relevant, the Min Heap model is usually favored on account of its effectiveness in sorting components the place decrease values signify larger precedence. I might be sharing an implementation that covers each circumstances on the finish of this text.
To be able to absolutely perceive Precedence Queues, a strong understanding of Heaps is crucial. Due to this fact the tone of this text is assuming you might be aware of the idea of Heaps. If that’s not the case otherwise you want a fast refreshment, I’d recommend you begin from the “Heap” article by following the hyperlink beneath, then come again and proceed right here later:
Deep dive into data structures using Javascript – Heap
Anatomy of a Precedence Queue
Precedence Queue format we’re discussing right here is constructed on high of Binary Heap, subsequently the anatomy is sort of an identical – besides one distinct facet: the utilization of a “precedence” property for every ingredient.
That is the characteristic the place Precedence Queue differs from a regular Heap. In a Min or Max heap, the position mechanism works primarily based on given worth, whereas within the Precedence Queue it’s primarily based on given precedence. The underlying structure of a Precedence Queue is usually an array, mirroring the array illustration of a Heap. On this array, every index doesn’t simply maintain a price however an object or a pair containing the worth and its precedence.
Check out the visible beneath to see the excellence between a Precedence Queue utilizing a Min Heap as underlying construction versus a daily Min Heap. Each are proven with their Binary Heap illustration, we add the identical values following the identical order. However there’s a small twist – every ingredient added to the Precedence Queue has completely different priorities assigned to them:
When to Use a Precedence Queue
Precedence Queues are principally suited to specific situations the place the order of merchandise processing is essential. Let’s begin with having a look on the Big O of frequent operations:
Insertion Operation (Enqueue): The insertion of a component, which entails including a price with a given precedence, sometimes requires O(log n) time complexity. The newly added ingredient could have to ascend in the direction of the entrance of the queue, particularly if it has a excessive precedence, respecting the queue’s ordering guidelines.
Removing Operation (Dequeue): Eradicating the ingredient with the very best precedence, which is mostly on the entrance of the queue, additionally takes O(log n) time complexity. This operation could set off a reorganization of the queue to make sure the subsequent highest precedence ingredient involves the forefront.
Peek Operation: Accessing the ingredient with the very best precedence is a continuing time operation, O(1), since it’s all the time on the entrance of the queue, able to be processed subsequent.
Replace Precedence Operation (non-compulsory): Updating the precedence of a component within the Precedence Queue can differ in time complexity relying on the underlying implementation.
- With a map: If an inner map is utilized to trace the indices and an exterior reference (ID) is stored for every ingredient, the
updatePriorityoperation could be carried out in O(log n) time complexity. It is because the map permits us to straight entry the ingredient within the heap, and the one remaining operation is the reorganization of the heap (heapify), which takes O(log n). - With no map: Within the absence of such a map, updating the precedence requires a linear search to search out the ingredient, leading to O(n) time complexity. After discovering the ingredient, we might nonetheless have to carry out the heap reorganization, however the dominant issue is the linear search time.
Search Operation (non-compulsory): Whereas not a main operate, trying to find a component in a Precedence Queue, on account of its array-based implementation, has a time complexity of O(n). It is because it might require a linear scan to discover a specific ingredient if its precedence is unknown.
Contemplating the time complexities above, Precedence Queues show to be exceptionally useful in a number of use circumstances:
Activity Scheduling: Precedence Queues are perfect for managing duties the place sure duties take priority over others on account of urgency or significance.
Simulation Methods: In simulations the place occasions are processed at various speeds or frequencies, Precedence Queues handle the occasion schedule successfully, ensuring high-priority occasions are processed first.
Dijkstra’s Algorithm for Shortest Paths: Similar to Heaps are utilized in graph algorithms, Precedence Queues are essential for effectively discovering the shortest path in a weighted graph the place the processing order of nodes is set by their path prices.
Load Balancing and Useful resource Administration: Methods that handle computing sources typically make the most of Precedence Queues to deal with jobs in line with their useful resource calls for or time constraints.
Actual-time Knowledge Processing: In methods the place knowledge is processed in real-time, equivalent to inventory worth updates or sensor knowledge, Precedence Queues makes certain that essentially the most essential knowledge is dealt with promptly.
Precedence Queue implementation in Javascript
We might be utilizing ES6 Lessons to construct our Precedence Queue. As talked about earlier, if we embrace an “updatePriority” methodology, we’d like 2 variations. One would want to contain inner map conserving monitor of indexes, whereas the opposite will not. Due to this fact I might be sharing each implementations:
- A easy model that doesn’t make the most of a map for monitoring ingredient indexes, appropriate for smaller knowledge units or when most efficiency will not be essential.
- An optimized model that features a map to effectively monitor and replace ingredient indexes, offering quicker lookup occasions that are important for bigger knowledge units.
Right here is the listing of strategies that we’re going to implement:
Easy Precedence Queue:
-
dimension(): Returns the present variety of gadgets within the precedence queue. -
isEmpty(): Determines whether or not the precedence queue is empty. -
peek(): Retrieves the ingredient with the very best precedence (the entrance of the queue) with out eradicating it. -
enqueue(worth, precedence): Inserts a brand new worth with its related precedence into the queue, adjusting the queue to keep up the precedence ordering. -
dequeue(): Removes and returns the ingredient with the very best precedence from the queue whereas preserving the precedence order of the remaining components. -
updatePriority(worth, newPriority, equalityFn): This methodology permits the precedence of an current ingredient within the queue to be modified. It first locates the ingredient inside the queue primarily based on a given worth, utilizing theequalityFnto find out equality. If the ingredient is discovered, its precedence is up to date to the brand new worth specified. The queue is then reorganized to keep up the proper precedence order. This reorganization entails both transferring the ingredient up (_heapifyUpFromIndex) if its new precedence is larger, or transferring it down (_heapifyDownFromIndex) if its new precedence is decrease in comparison with its unique precedence. This makes certain that the queue constantly maintains its precedence order even after the priorities of its components are altered. -
search(worth, equalityFn): (Non-compulsory) Locates a component inside the queue by its worth utilizing a customized equality operate, vital for the non-map-based implementation to replace priorities with out an exterior reference. -
toSortedArray(): (Non-compulsory) Returns the heap array in a sorted format. Sorting relies on the kind of Heap (Min or Max) the Precedence Queue is constructed upon. A Min Heap primarily based Precedence Queue could have the smallest ingredient on the first index, for Max Heap primarily based model is the alternative.
Utility strategies:
-
_parentIndex(i),_leftChildIndex(i),_rightChildIndex(i),_hasLeftChild(i),_hasRightChild(i): Utility strategies that help in navigating the inner heap construction of the precedence queue. -
_heapifyUp(),_heapifyDown(): Important strategies for sustaining the heap construction after insertions or deletions, helps to maintain the heap property of the queue primarily based on the precedence ordering. -
_heapifyUpFromIndex(i),_heapifyDownFromIndex(i): Important strategies for sustaining the heap construction after precedence updates, helps to maintain the heap property of the queue primarily based on the precedence ordering.
Optimized Precedence Queue:
Optimized model shares nearly all of strategies as the easy model, however there are a pair variations with the strategies beneath:
enqueue(worth, precedence): Whereas including a brand new ingredient, the optimized model not solely inserts the worth into the heap but in addition updates an inner map. This map tracks the index of every ingredient utilizing its distinctive ID as the important thing. This makes certain that the ingredient’s place could be rapidly referenced throughout future operations, offering a big efficiency increase for precedence updates.
dequeue(): The elimination course of within the optimized model is augmented by the need to keep up the inner map’s accuracy. After the very best precedence ingredient is faraway from the heap, the map is up to date to take away the entry similar to this ingredient’s ID. If the final ingredient within the heap is moved to the entrance (to exchange the eliminated high ingredient), the map can be up to date to mirror this new place. This makes certain that subsequent operations on the queue can proceed with essentially the most present data.
updatePriority(id, newPriority): This methodology within the optimized precedence queue is extra environment friendly model for updating the precedence of an current ingredient. The cornerstone of this optimization lies in using an inner map (this._map), which shops the indexes of components within the heap in opposition to their distinctive IDs. When this methodology is named, it first retrieves the ingredient’s index from the heap utilizing its distinctive ID, because of the map. This method is considerably extra environment friendly than looking by way of all the heap, because it permits for direct entry to the ingredient in fixed time.
As soon as the index is obtained, the strategy checks if the ingredient exists (if the index will not be undefined). If the ingredient is discovered, its precedence within the heap is up to date to the brand new worth. The queue then wants to regulate to keep up the precedence order. This adjustment depends upon whether or not the brand new precedence is larger or decrease than the previous one. For the next new precedence (a decrease numeric worth in a min-heap), the ingredient is moved up the heap utilizing _heapifyUpFromIndex. For a decrease new precedence (the next numeric worth), the strategy employs _heapifyDownFromIndex to maneuver the ingredient down the heap.
This map-based method within the optimized precedence queue is specifically helpful with massive knowledge units, or in situations the place frequent updates to priorities are frequent.
_generateId(): This methodology is a non-public utility operate used inside the optimized precedence queue class. Its goal is to generate a novel identifier (ID) for every new ingredient added to the queue. It really works by sustaining an inner counter (_nextId) that’s incremented every time a brand new ID is required. When referred to as, the strategy returns the present worth of _nextId after which increments the counter. This mechanism offers each ingredient within the queue a definite ID, which is essential for effectively updating a component’s precedence within the queue – as this ID is used to rapidly find the ingredient within the inner heap construction. This methodology is an important a part of the effectivity optimizations on this precedence queue implementation.
Precedence Queues could be initially difficult to know. As talked about earlier, I’d suggest getting aware of the underlying heap construction {that a} Precedence Queue is constructed upon — particularly, its array illustration. This entails understanding the right way to establish the mum or dad, left, and proper kids of any given ingredient utilizing easy array index calculations. As soon as comfy with navigating this construction, one ought to then discover the dynamic nature of Precedence Queues, specializing in how the enqueue and dequeue operations work in tandem with heapifyUp and heapifyDown to keep up order in line with precedence ranges.
Moreover, I’ve additionally included line-by-line explanations for every methodology within the implementation so that you can comply with up what is occurring within the code. I hope this text helped you to understand what Precedence Queues are and the way they work! I’d prefer to encourage you to experiment with the implementations beneath in your favourite code editor. Thanks for studying!
Easy Precedence Queue implementation:
class PriorityQueue {
// The constructor methodology is named when a brand new occasion of Precedence Queue is created.
constructor(comparator) ((a, b) => a - b);
// Return the variety of gadgets within the heap.
dimension() {
return this.heap.size;
}
// Examine if the heap is empty.
isEmpty() {
return this.dimension() === 0;
}
// Get the highest ingredient within the heap with out eradicating it.
// For a min-heap, this would be the smallest ingredient;
// for a max-heap, it is going to be the most important.
peek() {
return this.heap[0] ? this.heap[0].worth : null;
}
// Add a brand new worth to the heap.
enqueue(worth, precedence) {
// First, add the brand new worth to the top of the array.
this.heap.push({ worth, precedence });
// Then, transfer the brand new worth up the heap to its right place.
this._heapifyUp();
}
// Take away and return the highest ingredient within the heap.
dequeue() {
// If the heap is empty, simply return null
if (this.isEmpty()) {
return null;
}
// Save the highest ingredient so we are able to return it later
const poppedValue = this.peek();
// If there's a couple of node within the heap, transfer the final node to the highest.
const backside = this.dimension() - 1;
if (backside > 0) {
this._swap(0, backside);
}
// Take away the final node (which is now the highest node) from the heap.
this.heap.pop();
// Transfer the brand new high node down the heap to its right place.
this.heapifyDown();
// Lastly, return the unique high ingredient.
return poppedValue;
}
// This methodology updates the precedence of a selected worth within the heap.
updatePriority(worth, newPriority, equalityFn) {
// Discover the index of the merchandise within the heap that matches the given worth.
const index = this.heap.findIndex((merchandise) => equalityFn(merchandise.worth, worth));
// If the merchandise will not be discovered, exit the operate.
if (index === -1) {
return; // Merchandise not discovered
}
// Replace the precedence of the discovered merchandise to the brand new precedence.
const oldPriority = this.heap[index].precedence;
this.heap[index].precedence = newPriority;
// Re-heapify primarily based on whether or not the brand new precedence is larger or decrease than the previous precedence.
if (
this.comparator({ precedence: newPriority }, { precedence: oldPriority }) < 0
) {
// If the brand new precedence is larger, heapify up from the present index.
this._heapifyUpFromIndex(index);
} else {
// If the brand new precedence is decrease, heapify down from the present index.
this._heapifyDownFromIndex(index);
}
}
search(worth, equalityFn) {
// Discover the merchandise within the heap utilizing the supplied equality operate
const merchandise = this.heap.discover((merchandise) => equalityFn(merchandise.worth, worth));
return merchandise ? merchandise : null;
}
toSortedArray() {
const sortedList = [...this.heap];
return sortedList.kind((a, b) => this.comparator(a.precedence, b.precedence));
}
// ********************* Helper strategies beneath: *********************
// Technique to get the index of a node's mum or dad.
_parentIndex(index) {
/*
About Math.ground:
We take the ground worth of the division to
ensure that we get the closest decrease integer worth.
That is essential as a result of array indexes
are integer values and can't have fractional components.
*/
return Math.ground((index - 1) / 2);
}
// Technique to get the index of a node's left baby.
_leftChildIndex(index) {
return 2 * index + 1;
}
// Technique to get the worth of a node's proper baby.
_rightChildIndex(index) {
return 2 * index + 2;
}
// Technique to examine if a node has left baby.
// It returns true if the left baby index is inside the legitimate vary of heap indexes,
// which signifies {that a} left baby exists.
_hasLeftChild(index) {
return this._leftChildIndex(index) < this.dimension();
}
// Technique to examine if a node has proper baby.
// It returns true if the appropriate baby index is inside the legitimate vary of heap indexes,
// which signifies {that a} proper baby exists.
_hasRightChild(index) {
return this._rightChildIndex(index) < this.dimension();
}
// Technique to swap the values of two nodes within the heap.
_swap(i, j) {
// Swap the values of components at indices i and j with out utilizing a brief variable:
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// This methodology rearranges the heap after including a brand new ingredient.
_heapifyUp() {
// Begin with the final ingredient added to the heap
let nodeIndex = this.dimension() - 1;
// Loop till the node reaches the foundation or the heap property is maintained
whereas (
nodeIndex > 0 &&
// Examine the present node with its mum or dad
this.comparator(
this.heap[nodeIndex].precedence,
this.heap[this._parentIndex(nodeIndex)].precedence
) < 0
) {
// If the present node's precedence is larger than its mum or dad, swap them
this._swap(nodeIndex, this._parentIndex(nodeIndex));
// Transfer to the mum or dad node and proceed
nodeIndex = this._parentIndex(nodeIndex);
}
}
// This methodology rearranges the heap after eradicating the highest ingredient.
_heapifyDown() {
// Begin with the foundation node
let currNodeIndex = 0;
// Loop so long as the present node has a left baby
whereas (this._hasLeftChild(currNodeIndex)) {
// Assume the left baby is the smaller baby
let smallerChildIndex = this._leftChildIndex(currNodeIndex);
// Examine if the appropriate baby exists and is smaller than the left baby
if (
this._hasRightChild(currNodeIndex) &&
this.comparator(
this.heap[this._rightChildIndex(currNodeIndex)].precedence,
this.heap[smallerChildIndex].precedence
) < 0
) {
// If that's the case, the appropriate baby is the smaller baby
smallerChildIndex = this._rightChildIndex(currNodeIndex);
}
// If the present node is smaller than its smallest baby, the heap is right
if (
this.comparator(
this.heap[currNodeIndex].precedence,
this.heap[smallerChildIndex].precedence
) <= 0
) {
break;
}
// In any other case, swap the present node with its smallest baby
this._swap(currNodeIndex, smallerChildIndex);
// Transfer to the smaller baby and proceed
currNodeIndex = smallerChildIndex;
}
}
// This methodology rearranges the heap upwards from a given index.
_heapifyUpFromIndex(index) {
// Begin from the given index
let currentIndex = index;
// Proceed so long as the present index will not be the foundation
whereas (currentIndex > 0) {
// Discover the mum or dad index of the present index
let parentIndex = this._parentIndex(currentIndex);
// Examine the present node with its mum or dad
if (
this.comparator(this.heap[currentIndex], this.heap[parentIndex]) < 0
) {
// If present node is smaller than the mum or dad, swap them
this._swap(currentIndex, parentIndex);
// Transfer to the mum or dad node and proceed
currentIndex = parentIndex;
} else {
// If the present node will not be smaller than the mum or dad, cease the method
break;
}
}
}
// This methodology rearranges the heap downwards from a given index.
_heapifyDownFromIndex(index) {
// Begin from the given index
let currentIndex = index;
// Proceed so long as the present node has a left baby
whereas (this._hasLeftChild(currentIndex)) {
// Assume the left baby is the smaller baby
let smallerChildIndex = this._leftChildIndex(currentIndex);
// Examine if the appropriate baby exists and is smaller than the left baby
if (
this._hasRightChild(currentIndex) &&
this.comparator(
this.heap[this._rightChildIndex(currentIndex)],
this.heap[smallerChildIndex]
) < 0
) {
// If that's the case, the appropriate baby is the smaller baby
smallerChildIndex = this._rightChildIndex(currentIndex);
}
// If the present node is smaller or equal to its smallest baby, the heap is right
if (
this.comparator(
this.heap[currentIndex],
this.heap[smallerChildIndex]
) <= 0
) {
break;
}
// In any other case, swap the present node with its smallest baby
this._swap(currentIndex, smallerChildIndex);
// Transfer to the smaller baby and proceed
currentIndex = smallerChildIndex;
}
}
}
// Utilizing as MaxPriorityQueue:
class MaxPriorityQueue extends PriorityQueue {
constructor() {
// MaxPriorityQueue makes use of a comparator that types the inner heap in descending order
tremendous((a, b) => b - a);
}
}
// Utilization (works as MinPriorityQueue by default)
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue("A", 40);
priorityQueue.enqueue("B", 10);
priorityQueue.enqueue("C", 50);
priorityQueue.enqueue("D", 30);
priorityQueue.enqueue("E", 60);
priorityQueue.enqueue("G", 50);
priorityQueue.enqueue("F", 20);
priorityQueue.toSortedArray();
priorityQueue.updatePriority("A", 5, (a, b) => a === b);
priorityQueue.updatePriority("E", 7, (a, b) => a === b);
priorityQueue.toSortedArray();
Optimized Precedence Queue implementation:
class PriorityQueue {
// The constructor methodology is named when a brand new occasion of Precedence Queue is created.
constructor(comparator) ((a, b) => a - b);
// Map shops inner indexes for extra environment friendly updatePriority
this._map = new Map();
// Counter for the subsequent ID to assign
this._nextId = 0;
// Return the variety of gadgets within the heap.
dimension() {
return this.heap.size;
}
// Examine if the heap is empty.
isEmpty() {
return this.dimension() === 0;
}
// Get the highest ingredient within the heap with out eradicating it.
// For a min-heap, this would be the smallest ingredient;
// for a max-heap, it is going to be the most important.
peek() {
return this.heap[0] ? this.heap[0].worth : null;
}
// This methodology provides a brand new ingredient with its precedence into the precedence queue.
enqueue(worth, precedence) {
// Generate a novel identifier for the brand new ingredient.
const _id = this._generateId();
// Create an entry object containing the worth, precedence, and the generated ID.
const entry = { worth, precedence, _id };
// Add the brand new entry to the top of the heap array.
this.heap.push(entry);
// Retailer the index of this new entry within the map utilizing its ID for environment friendly lookups.
// That is essential for the updatePriority operation, permitting us to rapidly discover a component's index.
this._map.set(_id, this.heap.size - 1);
// Reorganize the heap to keep up the heap property after including a brand new ingredient.
// This ensures that the heap construction is maintained (both min-heap or max-heap).
this._heapifyUp();
// Return the distinctive ID of the brand new entry. This ID can be utilized later for operations like updatePriority.
return _id;
}
// This methodology removes and returns the ingredient with the very best precedence (on the root of the heap).
dequeue() {
// Examine if the heap is empty. Whether it is, return null.
if (this.isEmpty()) {
return null;
}
// The merchandise to be dequeued is all the time on the root of the heap (index 0).
const dequeuedItem = this.heap[0];
// Take away the dequeued merchandise's entry from the map utilizing its distinctive ID.
// This retains the map up to date with solely present heap components.
this._map.delete(dequeuedItem._id);
// Discover the index of the final ingredient within the heap.
const backside = this.dimension() - 1;
// Examine if there are extra components left within the heap after dequeuing.
if (backside > 0) {
// Substitute the foundation of the heap with the final ingredient.
this.heap[0] = this.heap[bottom];
// Replace the place of the moved merchandise within the map.
this._map.set(this.heap[0]._id, 0);
// Take away the final ingredient (now moved to the foundation) from the heap.
this.heap.pop();
// Reorganize the heap to keep up the heap property after the foundation change.
this._heapifyDown();
} else {
// If there is just one ingredient within the heap, take away it and clear the map.
this.heap.pop();
this._map.clear();
}
// Return the worth of the dequeued merchandise.
return dequeuedItem.worth;
}
// This methodology updates the precedence of a component within the precedence queue.
updatePriority(id, newPriority) {
// Retrieve the index of the ingredient within the heap utilizing the distinctive ID from the map.
const index = this._map.get(id);
// If the ingredient with the given ID will not be discovered within the map, exit the operate early.
if (index === undefined) {
return;
}
// Retrieve the previous precedence of the ingredient for comparability.
const oldPriority = this.heap[index].precedence;
// Replace the precedence of the ingredient within the heap with the brand new precedence.
this.heap[index].precedence = newPriority;
// Determine whether or not to heapify up or down primarily based on the brand new precedence.
// If the brand new precedence is larger (smaller worth for min-heap), heapify up.
// If the brand new precedence is decrease (bigger worth for min-heap), heapify down.
if (
this.comparator({ precedence: newPriority }, { precedence: oldPriority }) < 0
) {
this._heapifyUpFromIndex(index);
} else {
this._heapifyDownFromIndex(index);
}
}
search(worth, equalityFn) {
// Discover the merchandise within the heap utilizing the supplied equality operate
const merchandise = this.heap.discover((merchandise) => equalityFn(merchandise.worth, worth));
return merchandise ? merchandise : null;
}
toSortedArray() {
const sortedList = [...this.heap];
return sortedList.kind((a, b) => this.comparator(a.precedence, b.precedence));
}
// ********************* Helper strategies beneath: *********************
// Technique to generate distinctive ID for inner lookup map
_generateId() {
return this._nextId++; // Increment the ID counter and return the brand new ID
}
// Technique to get the index of a node's mum or dad.
_parentIndex(index) {
/*
About Math.ground:
We take the ground worth of the division to
ensure that we get the closest decrease integer worth.
That is essential as a result of array indexes
are integer values and can't have fractional components.
*/
return Math.ground((index - 1) / 2);
}
// Technique to get the index of a node's left baby.
_leftChildIndex(index) {
return 2 * index + 1;
}
// Technique to get the worth of a node's proper baby.
_rightChildIndex(index) {
return 2 * index + 2;
}
// Technique to examine if a node has left baby.
// It returns true if the left baby index is inside the legitimate vary of heap indexes,
// which signifies {that a} left baby exists.
_hasLeftChild(index) {
return this._leftChildIndex(index) < this.dimension();
}
// Technique to examine if a node has proper baby.
// It returns true if the appropriate baby index is inside the legitimate vary of heap indexes,
// which signifies {that a} proper baby exists.
_hasRightChild(index) {
return this._rightChildIndex(index) < this.dimension();
}
// Technique to swap the values of two nodes within the heap.
_swap(i, j) {
// Swap the weather within the heap array at indices i and j.
// That is generally wanted throughout heapify operations to keep up the heap invariant.
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
// After swapping the weather within the heap array, their positions (indices) have modified.
// We should replace the map to mirror these new positions.
// Set the map entry for the ingredient that was initially at index i (now at index j)
// to the brand new index (j). The _id property is used as the important thing within the map.
this._map.set(this.heap[i]._id, i);
// Equally, set the map entry for the ingredient that was initially at index j (now at index i)
// to the brand new index (i). As earlier than, the _id property is used as the important thing within the map.
this._map.set(this.heap[j]._id, j);
}
// This methodology rearranges the heap after including a brand new ingredient.
_heapifyUp() {
// Begin with the final ingredient added to the heap
let nodeIndex = this.dimension() - 1;
// Loop till the node reaches the foundation or the heap property is maintained
whereas (
nodeIndex > 0 &&
// Examine the present node with its mum or dad
this.comparator(
this.heap[nodeIndex].precedence,
this.heap[this._parentIndex(nodeIndex)].precedence
) < 0
) {
// If the present node's precedence is larger than its mum or dad, swap them
this._swap(nodeIndex, this._parentIndex(nodeIndex));
// Transfer to the mum or dad node and proceed
nodeIndex = this._parentIndex(nodeIndex);
}
}
// This methodology rearranges the heap after eradicating the highest ingredient.
_heapifyDown() {
// Begin with the foundation node
let currNodeIndex = 0;
// Loop so long as the present node has a left baby
whereas (this._hasLeftChild(currNodeIndex)) {
// Assume the left baby is the smaller baby
let smallerChildIndex = this._leftChildIndex(currNodeIndex);
// Examine if the appropriate baby exists and is smaller than the left baby
if (
this._hasRightChild(currNodeIndex) &&
this.comparator(
this.heap[this._rightChildIndex(currNodeIndex)].precedence,
this.heap[smallerChildIndex].precedence
) < 0
) {
// If that's the case, the appropriate baby is the smaller baby
smallerChildIndex = this._rightChildIndex(currNodeIndex);
}
// If the present node is smaller than its smallest baby, the heap is right
if (
this.comparator(
this.heap[currNodeIndex].precedence,
this.heap[smallerChildIndex].precedence
) <= 0
) {
break;
}
// In any other case, swap the present node with its smallest baby
this._swap(currNodeIndex, smallerChildIndex);
// Transfer to the smaller baby and proceed
currNodeIndex = smallerChildIndex;
}
}
// This methodology rearranges the heap upwards from a given index.
_heapifyUpFromIndex(index) {
// Begin from the given index
let currentIndex = index;
// Proceed so long as the present index will not be the foundation
whereas (currentIndex > 0) {
// Discover the mum or dad index of the present index
let parentIndex = this._parentIndex(currentIndex);
// Examine the present node with its mum or dad
if (
this.comparator(this.heap[currentIndex], this.heap[parentIndex]) < 0
) {
// If present node is smaller than the mum or dad, swap them
this._swap(currentIndex, parentIndex);
// Transfer to the mum or dad node and proceed
currentIndex = parentIndex;
} else {
// If the present node will not be smaller than the mum or dad, cease the method
break;
}
}
}
// This methodology rearranges the heap downwards from a given index.
_heapifyDownFromIndex(index) {
// Begin from the given index
let currentIndex = index;
// Proceed so long as the present node has a left baby
whereas (this._hasLeftChild(currentIndex)) {
// Assume the left baby is the smaller baby
let smallerChildIndex = this._leftChildIndex(currentIndex);
// Examine if the appropriate baby exists and is smaller than the left baby
if (
this._hasRightChild(currentIndex) &&
this.comparator(
this.heap[this._rightChildIndex(currentIndex)],
this.heap[smallerChildIndex]
) < 0
) {
// If that's the case, the appropriate baby is the smaller baby
smallerChildIndex = this._rightChildIndex(currentIndex);
}
// If the present node is smaller or equal to its smallest baby, the heap is right
if (
this.comparator(
this.heap[currentIndex],
this.heap[smallerChildIndex]
) <= 0
) {
break;
}
// In any other case, swap the present node with its smallest baby
this._swap(currentIndex, smallerChildIndex);
// Transfer to the smaller baby and proceed
currentIndex = smallerChildIndex;
}
}
}
// Utilizing as MaxPriorityQueue:
class MaxPriorityQueue extends PriorityQueue {
constructor() {
// MaxPriorityQueue makes use of a comparator that types the inner heap in descending order
tremendous((a, b) => b - a);
}
}
// Utilization (works as MinPriorityQueue by default)
// Utilization
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue("A", 40);
priorityQueue.enqueue("B", 10);
priorityQueue.enqueue("C", 50);
priorityQueue.enqueue("D", 30);
priorityQueue.enqueue("E", 60);
// hold monitor of ids:
const idJohn = priorityQueue.enqueue({ message: "hey", title: "john" }, 22);
const idA = priorityQueue.enqueue("F", 20);
console.log("BEFORE:");
priorityQueue.toSortedArray();
console.log("AFTER:");
// Now use the ID to replace the precedence
priorityQueue.updatePriority(idA, 1);
priorityQueue.updatePriority(idJohn, 55);
priorityQueue.toSortedArray();
