Heap | Priority Queue Implementation using Javascript
Introduction
A heap is a special tree-based data structure that satisfies the heap property.
It is a complete binary tree, which means all levels of the tree are fully filled except for the last level, which is filled from left to right.
There are two types of heaps:
- max heap
- min heap.
Max Heap:
In a max heap, for any given node I, the value of I is greater than or equal to the values of its children.
This property must be true for all nodes in the Binary Tree. The highest value (maximum) is at the root of the tree.
Min Heap:
In a min heap, for any given node I, the value of I is less than or equal to the values of its children.
This property must be true for all nodes in the Binary Tree. The lowest value (minimum) is at the root of the tree.
We can call them a priority queue as every time we do an insert and delete operation it will bubbleUp and bubbleDown respectively.
We can implement the same in an array but how to calculate the leftChildindex, rightChildIndex and parentIndex?
Formula
To get child
2i+1(left )
2i+2 (right)
To get parent
i-1/2
Below I added an implementation of minHeap please check.
class MinHeap {
constructor() {
this.data = [];
this.length = 0;
}
insert(value) {
this.data.push(value);
this.length++;
this.bubbleUp(this.length-1);
}
bubbleUp(index) {
if (index == 0) {
return ;
}
const parentIndex = this.getParentIndex(index);
const parentValue = this.data[parentIndex];
const value = this.data[index];
if (parentValue > value) {
this.data[parentIndex] = this.data[index];
this.data[index] = parentValue;
this.bubbleUp(parentIndex);
}
}
getParentIndex(index) {
return Math.floor((index-1)/2);
}
getLeftChildIndex(index) {
return 2*index + 1;
}
getRightChildIndex(index) {
return 2*index + 2;
}
bubbleDown(index) {
if (index >= this.length) {
return;
}
const lIndex = this.getLeftChildIndex(index);
const rIndex = this.getRightChildIndex(index);
const lValue = this.data[lIndex];
const rValue = this.data[rIndex];
const value = this.data[index];
if (lValue < rValue && lValue < value) {
// swap
this.data[index] = this.data[lIndex];
this.data[lIndex] = value;
this.bubbleDown(lIndex);
} else if (rValue < lValue && rValue < value) {
this.data[index] = this.data[rIndex];
this.data[rIndex] = value;
this.bubbleDown(rIndex)
}
}
delete() {
if (this.length === 0) {
return -1;
}
const out = this.data[0];
if (this.length == 1) {
this.data = [];
this.length = 0;
return out;
}
this.data[0] = this.data[this.length-1];
this.length--;
this.bubbleDown(0);
}
}
const test = new MinHeap();
test.insert(50);
test.insert(100);
test.insert(101);
test.insert(20);
test.insert(110);
console.log(test)
test.delete();
console.log('---------After Delete -------')
console.log(test)
/*
MinHeap { data: [ 20, 50, 101, 100, 110 ], length: 5 }
---------After Delete -------
MinHeap { data: [ 50, 100, 101, 110, 110 ], length: 4 }
*/
Let me know of you have any queries, feel free to connect.
The above is the detailed content of Heap | Priority Queue Implementation using Javascript. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undress AI Tool
Undress images for free
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Advanced Conditional Types in TypeScript
Aug 04, 2025 am 06:32 AM
TypeScript's advanced condition types implement logical judgment between types through TextendsU?X:Y syntax. Its core capabilities are reflected in the distributed condition types, infer type inference and the construction of complex type tools. 1. The conditional type is distributed in the bare type parameters and can automatically split the joint type, such as ToArray to obtain string[]|number[]. 2. Use distribution to build filtering and extraction tools: Exclude excludes types through TextendsU?never:T, Extract extracts commonalities through TextendsU?T:Never, and NonNullable filters null/undefined. 3
Micro Frontends Architecture: A Practical Implementation Guide
Aug 02, 2025 am 08:01 AM
Microfrontendssolvescalingchallengesinlargeteamsbyenablingindependentdevelopmentanddeployment.1)Chooseanintegrationstrategy:useModuleFederationinWebpack5forruntimeloadingandtrueindependence,build-timeintegrationforsimplesetups,oriframes/webcomponents
What are the differences between var, let, and const in JavaScript?
Aug 02, 2025 pm 01:30 PM
varisfunction-scoped,canbereassigned,hoistedwithundefined,andattachedtotheglobalwindowobject;2.letandconstareblock-scoped,withletallowingreassignmentandconstnotallowingit,thoughconstobjectscanhavemutableproperties;3.letandconstarehoistedbutnotinitial
What is optional chaining (?.) in JS?
Aug 01, 2025 am 06:18 AM
Optionalchaining(?.)inJavaScriptsafelyaccessesnestedpropertiesbyreturningundefinedifanypartofthechainisnullorundefined,preventingruntimeerrors.1.Itallowssafeaccesstodeeplynestedobjectproperties,suchasuser.profile?.settings?.theme.2.Itenablescallingme
Generate Solved Double Chocolate Puzzles: A Guide to Data Structures and Algorithms
Aug 05, 2025 am 08:30 AM
This article explores in-depth how to automatically generate solveable puzzles for the Double-Choco puzzle game. We will introduce an efficient data structure - a cell object based on a 2D grid that contains boundary information, color, and state. On this basis, we will elaborate on a recursive block recognition algorithm (similar to depth-first search) and how to integrate it into the iterative puzzle generation process to ensure that the generated puzzles meet the rules of the game and are solveable. The article will provide sample code and discuss key considerations and optimization strategies in the generation process.
How can you remove a CSS class from a DOM element using JavaScript?
Aug 05, 2025 pm 12:51 PM
The most common and recommended method for removing CSS classes from DOM elements using JavaScript is through the remove() method of the classList property. 1. Use element.classList.remove('className') to safely delete a single or multiple classes, and no error will be reported even if the class does not exist; 2. The alternative method is to directly operate the className property and remove the class by string replacement, but it is easy to cause problems due to inaccurate regular matching or improper space processing, so it is not recommended; 3. You can first judge whether the class exists and then delete it through element.classList.contains(), but it is usually not necessary; 4.classList
What is the class syntax in JavaScript and how does it relate to prototypes?
Aug 03, 2025 pm 04:11 PM
JavaScript's class syntax is syntactic sugar inherited by prototypes. 1. The class defined by class is essentially a function and methods are added to the prototype; 2. The instances look up methods through the prototype chain; 3. The static method belongs to the class itself; 4. Extends inherits through the prototype chain, and the underlying layer still uses the prototype mechanism. Class has not changed the essence of JavaScript prototype inheritance.
Vercel SPA routing and resource loading: Solve deep URL access issues
Aug 13, 2025 am 10:18 AM
This article aims to solve the problem of deep URL refresh or direct access causing page resource loading failure when deploying single page applications (SPAs) on Vercel. The core is to understand the difference between Vercel's routing rewriting mechanism and browser parsing relative paths. By configuring vercel.json to redirect all paths to index.html, and correct the reference method of static resources in HTML, change the relative path to absolute path, ensuring that the application can correctly load all resources under any URL.
