NFT Dashboard Application Development.
Through a wide variety of mobile applications, we’ve developed a unique visual system.
- Client George Wallace
- Date 15 June 2022
- Services Web Application
- Budget $100000+
Xinrui's personal website that shares my work and thoughts
I use animation as a third dimension by which to simplify experiences and kuiding thro each and every interaction. I’m not adding motion just to spruce things up, but doing it in ways that.
Qualitative Research, Quantitative Research, Heuristic Evaluation, Competitor Analysis, Usability Testing
We make tailor-made user acquisition to increase business growth for you to uncover all the potential opportunities!
Through a wide variety of mobile applications, we’ve developed a unique visual system.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
A strategy is a general plan to achieve one or more long-term. labore et dolore magna aliqua.
UI/UX Design, Art Direction, A design is a plan or specification for art. which illusively scale lofty heights.
User experience (UX) design is the process design teams use to create products that provide.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications.
UI/UX Design, Art Direction, A design is a plan or specification for art viverra maecenas accumsan.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
The training provided by universities in order to prepare me to work in various sectors of the computer science area.
I get my foundation of CS built here, I learn from the lower level operation system, network, Assembly language to Database, Java and data structure.
Using React, Redux, React Query, Webpack and TypeScript to build AWS IAM Console, integrate with backend APIs, develop a widget system that can plug and play with other AWS Console.
Re-design the Expedia checkout insurance module experience, re-write the jQuery based module to React widgets.
The India economy has grown strongly over recent years, having transformed itself from a producer and innovation-based economy.
App Generator is an all-in-one platform designed for businesses or individuals lacking a development team but wishing to create their own video app. It utilizes technologies such as Angular, Java, and Swift to offer a user-friendly interface where users can select their desired video content and target platform. Ultimately, it generates a customizable app tailored to their needs. Additionally, the platform allows for on-the-fly updates to app content and themes, eliminating the need for frequent app version upgrades.
The AWS IAM Console, ranking as the third most trafficked service on the AWS platform, currently operates on an outdated framework that incorporates a blend of technologies like AngularJS 1.6, Backbone, and Ruby, making it challenging to read and maintain. We are embarking on a complete overhaul of the entire IAM console to enhance usability and maintainability. By adopting modern technologies such as React, Redux, TypeScript, React Query, and REST API, we aim to streamline the architecture while preserving the original user experience.
I spearheaded the frontend segment of the re:Invent project titled "Least Privilege Policy Generator." This tool is designed to analyze a policy over a certain period, identify the services accessed, and refine the policy to limit its scope to only necessary permissions. Consequently, it mitigates the risk associated with granting overly broad policies to unintended recipients.
I have successfully completed scuba diving training and achieved certifications in various disciplines, including PADI Open Water, Advanced Open Water, Enriched Air Diver, and EFR-Primary Care (CPR) & Secondary Care. Additionally, I am an SSI-certified Freediver.
I have developed numerous websites, including e-commerce platforms for companies such as Biovive, Reflexgroup, and WolfTech Studio, showcasing this very site as an example of my work. Leveraging my extensive experience, I also mentor individuals aspiring to learn website development. My expertise spans across all web technologies, from historical methods like modifying HTML/CSS for IE6 compatibility, crafting class-like JavaScript structures before the advent of ES6 and TypeScript, to implementing functionalities traditionally handled by modern frameworks like React and Bootstrap using plain JavaScript/CSS. Furthermore, I am skilled in creating responsive designs with pure CSS, alongside other now less commonly discussed techniques.
I Like many others, I enjoy playing video games, which inspired me to learn how to create them myself. I self-taught various game engines, including Phaser, Unity, and Three.js, and have used these tools to develop games such as Flappy Bird and Ping-Pong, among others.
I write scripts to automate some tasks, mostly using Cypress Integration Test framework.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
Maecenas finibus nec sem ut imperdiet. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante. Ut tincidunt est ac dolor aliquam sodales phasellus smauris test
Maecenas finibus nec sem ut imperdiet. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante. Ut tincidunt est ac dolor aliquam sodales phasellus smauris
Maecenas finibus nec sem ut imperdiet. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante. Ut tincidunt est ac dolor aliquam sodales phasellus smauris
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
1 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
2 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
8 Plugins/Extensions
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
5 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
5 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
50 Plugins/Extensions
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
10 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
20 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
100 Plugins/Extensions
Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.
A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.
TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.
First, let’s create a PriorityQueue
class that will hold our heap.
class PriorityQueue<T> {
private heap: T[] = [];
constructor(private comparator: (a: T, b: T) => number) {}
}
We need a method to swap two elements in the heap.
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
Calculate the indices of parent and child nodes.
private parentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
private leftChildIndex(index: number): number {
return 2 * index + 1;
}
private rightChildIndex(index: number): number {
return 2 * index + 2;
}
Add a new element to the heap and reorder it to maintain the heap property.
push(item: T): void {
this.heap.push(item);
this.heapifyUp();
}
Move the new element up to its correct position.
private heapifyUp(): void {
let index = this.heap.length - 1;
while (
index > 0 &&
this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
Remove and return the element with the highest priority.
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const item = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown();
return item;
}
Reorder the heap after removing the root element.
private heapifyDown(): void {
let index = 0;
const length = this.heap.length;
while (this.leftChildIndex(index) < length) {
let smallestChildIndex = this.leftChildIndex(index);
const rightChildIdx = this.rightChildIndex(index);
if (
rightChildIdx < length &&
this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
) {
smallestChildIndex = rightChildIdx;
}
if (
this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
) {
break;
}
this.swap(index, smallestChildIndex);
index = smallestChildIndex;
}
}
Get the element with the highest priority without removing it and get the size of the queue.
peek(): T | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
Now, we’ll implement an update()
method that allows us to update the priority of an element, either by its index or by its value.
updateAt(index: number, newValue: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error("Index out of bounds");
}
const oldValue = this.heap[index];
this.heap[index] = newValue;
if (this.comparator(newValue, oldValue) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.
Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.
update(value: T, newValue: T): void {
const index = this.heap.findIndex((element) => element === value);
if (index === -1) {
throw new Error("Value not found in heap");
}
this.updateAt(index, newValue);
}
Explanation: We find the index of the value in the heap and then call updateAt()
to update it.
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
We’ll add a heapify()
method to build a heap from an existing array.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Now, let’s use our PriorityQueue
to find the Kth largest element in an array.
Given an integer array nums
and an integer k
, return the kth
largest element in the array.
We’ll use a min-heap (priority queue) to keep track of the largest k
elements.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => a - b);
for (const num of nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.peek() as number;
}
Comparator: (a, b) => a - b
ensures a min-heap.
Logic: Maintain a heap of size k
. The root will be the kth largest element.
Full Code Listing with small changes in variable names
class PriorityQueue<T> {
private heap: T[];
constructor(private compare: (a: T, b: T) => number) {
this.heap = [];
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
private parent(i: number): number {
return Math.floor((i - 1) / 2);
}
private left(i: number): number {
return 2 * i + 1;
}
private right(i: number): number {
return 2 * i + 2;
}
private heapifyUp(index: number): void {
while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
this.swap(index, this.parent(index));
index = this.parent(index);
}
}
private heapifyDown(index: number): void {
const length = this.heap.length;
while (this.left(index) < length) {
let smallest = this.left(index);
const rightIndex = this.right(index);
if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
smallest = rightIndex;
}
if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
break;
}
this.swap(index, smallest);
index = smallest;
}
}
public push(item: T): void {
this.heap.push(item);
this.heapifyUp(this.heap.length - 1);
}
public pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown(0);
return root;
}
public peek(): T | undefined {
return this.heap[0];
}
public size(): number {
return this.heap.length;
}
public updateAtIndex(index: number, newItem: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
this.heap[index] = newItem;
if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
public update(item: T, newItem: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.updateAtIndex(index, newItem);
}
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
public isEmpty(): boolean {
return this.heap.length === 0;
}
public heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
}
Let’s test our implementation with an example.
const nums = [3, 2, 1, 5, 6, 4];
const k = 2;
const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5
heapify()
to Build a Heap from an ArraytypescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);
console.log(pq.peek()); // Output: 1
findKthLargest
Function Using heapify()
We can optimize our earlier findKthLargest
function by using heapify()
.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap
pq.heapify(nums);
for (let i = 0; i < k - 1; i++) {
pq.pop();
}
return pq.peek() as number;
}
heapifyDown()
in heapify()
?That’s a great question! In the heapify()
method, we use heapifyDown()
instead of heapifyUp()
because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.
When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown()
on each node. This process is known as the heapify algorithm or build heap.
heapifyDown()
, the overall time complexity of building the heap is O(n). If we were to use heapifyUp()
, the time complexity would increase to O(n log n) in the worst case.heapifyDown()
can fix all violations of the heap property from the current node down to the leaves in one pass, whereas heapifyUp()
might require multiple passes for each node.heapifyDown()
is more appropriate when you need to adjust the heap starting from the internal nodes downwards.heapifyUp()
is typically used when inserting a new element into an already built heap.When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Math.floor(this.heap.length / 2) - 1
Math.floor(n/2)
to n - 1
are all leaf nodes.heapifyUp()
?
heapifyUp()
is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.heapifyUp()
during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels.heapifyDown()
can adjust the subtree rooted at a node in one pass.Suppose we have an array [3, 2, 1, 5, 6, 4]
and we want to build a min-heap.
this.heap = [3, 2, 1, 5, 6, 4];
Math.floor(6 / 2) - 1 = 2
.heapifyDown()
on Index 2:
1
, and its children are out of bounds, so no action is needed.heapifyDown()
on Index 1:
2
, with left child 5
and right child 6
.2
is less than its children, no action is needed.heapifyDown()
on Index 0:3
, with left child 2
and right child 1
.The right child 1
is the smallest, so we swap 3
with 1
.[1, 2, 3, 5, 6, 4]
.heapifyDown()
on the Swapped Node:
3
) has a left child 4
, but since 3
is less than 4
, no further action is needed.heapifyDown()
:
heapifyUp()
:
Therefore, in the heapify()
method, we choose heapifyDown()
to efficiently build a valid heap from the bottom up.
heapifyUp()
?
heapifyUp()
on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity.heapifyDown()
allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.heapifyDown()
: Total time complexity is O(n).heapifyUp()
: Total time complexity is O(n log n).We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.
大家好!今天我想和大家分享如何使用TypeScript实现一个优先队列(Priority Queue),并利用它来解决LeetCode第215题——数组中的第K个最大元素。在算法面试中,优先队列是一个非常常用的数据结构,理解并能熟练实现它对我们解决一系列问题都有帮助。
LeetCode第215题:数组中的第K个最大元素
给定一个未排序的整数数组 nums
,找到其中第 k
个最大的元素。
示例:
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
要找到第 k
个最大的元素,我们可以采用多种方法:
k
个最大的元素。时间复杂度为 O(n log n)。k
的最小堆来维护当前最大的 k
个元素。时间复杂度为 O(n log k)。在这篇文章中,我们重点介绍使用最小堆实现的优先队列,因为它在实际应用中非常高效,且实现相对简单。
优先队列是一种特殊的队列,元素按照优先级进行出入队操作。常用的实现方式是堆,根据堆的性质,可以快速地获取当前的最值(最大值或最小值)。
在我们的问题中,我们需要维护一个大小为 k
的最小堆,堆顶元素就是当前第 k
个最大的元素。
class MinHeap {
private heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
this.bubbleUp();
}
private bubbleUp(): void {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin(): number | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const end = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return min;
}
private sinkDown(): void {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * index + 1;
let rightChildIdx = 2 * index + 2;
let swapIdx: number | null = null;
if (leftChildIdx < length) {
if (this.heap[leftChildIdx] < element) {
swapIdx = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(swapIdx === null && this.heap[rightChildIdx] < element) ||
(swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
) {
swapIdx = rightChildIdx;
}
}
if (swapIdx === null) break;
[this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
index = swapIdx;
}
}
getMin(): number | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
}
bubbleUp
进行上浮操作,保持最小堆性质。sinkDown
进行下沉操作。k
的最小堆。k
时,移除堆顶元素(最小值)。k
个最大元素。function findKthLargest(nums: number[], k: number): number {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.size() > k) {
minHeap.extractMin();
}
}
return minHeap.getMin()!;
}
k
,则移除堆顶元素,确保堆中始终只包含当前最大的 k
个元素。k
个最大元素。const nums1 = [3, 2, 1, 5, 6, 4];
const k1 = 2;
console.log(findKthLargest(nums1, k1)); // 输出: 5
const nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
const k2 = 4;
console.log(findKthLargest(nums2, k2)); // 输出: 4
n
的数组,总的时间复杂度为 O(n log k),当 k
远小于 n
时,效率较高。通过使用最小堆实现的优先队列,我们可以高效地找到数组中的第 k
个最大元素。这种方法在处理大规模数据时非常实用,因为我们不需要对整个数组进行排序,只需维护一个大小为 k
的堆即可。
k
个最大元素时,此方法非常适用。希望这篇文章能帮助大家理解如何在TypeScript中实现优先队列,并应用于实际问题。如果有任何疑问或改进建议,欢迎在评论区与我交流!
感谢阅读!如果觉得有帮助,请点赞支持。
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head
of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr
be a node with a child list. The nodes in the child list should appear after curr
and before curr.next
in the flattened list.
Return the head
of the flattened list. The nodes in the list must have all of their child pointers set to null
.
Example 1:
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:
Example 2:
Input: head = [1,2,null,3] Output: [1,3,2] Explanation: The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:
Example 3:
Input: head = [] Output: [] Explanation: There could be empty list in the input.
Constraints:
1000
.1 <= Node.val <= 105
How the multilevel linked list is represented in test cases:
We use the multilevel linked list from Example 1 above:
1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL
The serialization of each level is as follows:
[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]
To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:
[1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null]
Merging the serialization of each level and removing trailing nulls we obtain:
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
The goal is to flatten a multilevel doubly linked list. Each node has next
, prev
, and child
pointers. The child
pointer points to another doubly linked list, which might have its own child
pointers. We need to flatten this structure into a single-level doubly linked list.
current
.child
, we need to:
next
node.child
list recursively.child
list between the current node and the next node.next
and prev
).child
pointer is set to null
.Code with Detailed Comments
var flatten = function(head) {
if (head === null) return null;
// Start traversing from the head node
let current = head;
// Traverse the entire linked list
while (current !== null) {
// If the current node has a child, we need to flatten it
if (current.child !== null) {
// Store the next node temporarily
let next = current.next;
// Recursively flatten the child list
let child = flatten(current.child);
// Insert the flattened child list
current.next = child;
child.prev = current;
// Find the tail of the flattened child list
while (child.next !== null) {
child = child.next;
}
// Connect the tail of the flattened child list to the next node
if (next !== null) {
next.prev = child;
}
child.next = next;
// Remove the child pointer
current.child = null;
}
// Move to the next node
current = current.next;
}
return head;
};
head
is null
. If it is, return null
immediately.current
to start from the head
node.while
loop to traverse the entire linked list.child
:
current
has a child
, perform the following steps:
next
node (current.next
).child
list by calling flatten(current.child)
.child
list between the current
node and the next
node:
current.next
to the head of the flattened child
list.prev
pointer of the flattened child
list head to point to current
.child
list by iterating through it until child.next
is null
.child
list to the next
node:
next.prev
to the tail of the flattened child
list (if next
is not null
).next
pointer of the tail of the flattened child
list to next
.current.child
to null
as it is now flattened and integrated into the main list.current
to the next node (current.next
) and repeat the process until the end of the list is reached.This approach ensures that all pointers are correctly updated, maintaining the doubly linked structure while flattening the multilevel list into a single-level list.
I am available for freelance work. Connect with me via and call in to my account.
Phone: (555) 345 678 90 Email: admin@example.com