Xinrui's personal website that shares my work and thoughts
Hi, I’m William Lina
Explore the professional journey, expertise, and achievements of a dedicated medical practitioner. Discover education, experience, clinical skills, research, and patient care .
Special Facilities For Our Patients
Rehabilitation Retreat
A serene haven dedicated to physical and emotional recovery, providing specialized therapies.
Adventure Basecamp
An adventure facility providing equipment, training, and guided experiences.
Child Development
A nurturing environment for children's growth and learning, equipped with a range of developmental programs.
Dr. Laura Jerry
Dr. Laura Jerry brings a wealth of experience and expertise to her practice. With a focus on patient-centered care, she is known for her warm and empathetic approach, always taking the time to listen to her patients’ concerns. Her extensive medical knowledge and dedication to staying at the forefront of the field make her a trusted healthcare partner.
Explore the range of medical services Dr. Collins offers, including general check-ups, preventative care, chronic disease management, and more. She is committed to working with you to develop personalized treatment plans that suit your unique needs.
Services For You &
Your Family
Pediatric Healthcare
Your first line of defense in health. Our primary care services cover check-ups and vaccinations.
Specialist Care
Access to top medical specialists for in-depth evaluation and treatment of specific health conditions.
Women's Health
Tailored healthcare services for women, including gynecology, obstetrics, and reproductive health.
Geriatric Care
Specialized care for our senior patients, focusing on age-related health issues chronic disease.
Diagnostic Testing
State-of-the-art diagnostic services, including imaging, laboratory tests, and screenings
Testimonial
Nevine Acotanza
Chief Operating OfficerChief Operating Officer
Mar 4, 2015 - Aug 30, 2021 testMr. Lee displayed remarkable responsiveness, professionalism, expertise, and proficiency. He swiftly grasped the intended concept and guided me in creating an elegant and captivating presentation.
Jone Duone Joe
Operating OfficerOperating Officer
Mar 4, 2016 - Aug 30, 2021Sarah exhibited remarkable responsiveness, professionalism, knowledge, and expertise. She quickly understood the intended concept and guided me in creating a sleek and aesthetically pleasing presentation.
Nevine Dhawan
CEO Of OfficerCEO Of Officer
Mar 4, 2016 - Aug 30, 2021Maecenas 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
My Regular Scedule
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Latest News
Unlocking the Lock: Solving the “Open the Lock” Problem with BFS
Today, we’re diving into a classic interview problem, Open the Lock. This problem requires us to use Breadth-First Search (BFS) to find the shortest path by simulating a lock mechanism with four wheels. Let’s walk through the problem step-by-step, analyze the solution, and cover key details in the code.
Problem Overview
The problem describes a lock with four rotating wheels, each numbered from 0 to 9. The lock starts at “0000”, and each wheel can be rotated up or down to the next number. For instance, “0” can rotate to “1” or “9”.
We have a list of deadend combinations. If we reach one of these, the lock stops, and we can’t proceed further from that position. Given these constraints, we need to find the minimum number of moves to turn the lock from “0000” to a target combination target
. If it’s impossible, we return -1.
Approach
Since we’re trying to find the shortest path to the target, this problem is a perfect candidate for Breadth-First Search (BFS). BFS explores all paths level by level, ensuring we reach the target in the fewest moves possible.
Step-by-Step Solution Outline:
- Initialization: Store all deadends in a
Set
for quick lookup. - BFS: Begin from “0000” and explore every possible combination by turning each wheel up or down.
- Track Moves: Use a queue to store each combination and the current move count, increasing it by one each level.
Code Implementation with Comments
/**
* @param {string[]} deadends - List of dead-end combinations
* @param {string} target - Target combination
* @return {number} - Minimum moves to reach target from "0000", or -1 if impossible
*/
var openLock = function(deadends, target) {
// Initialize a Set for deadends for quick lookup
const seen = new Set(deadends);
// Handle edge cases: if "0000" or target is in deadends, we can't proceed
if (seen.has(target) || seen.has('0000')) return -1;
// If the start is already the target, no moves are needed
if (target === '0000') return 0;
// Initialize BFS queue and moves counter
const queue = ["0000"];
seen.add("0000"); // Mark "0000" as visited
let steps = 0;
// Main BFS loop
while (queue.length > 0) {
// Number of nodes in the current level
let size = queue.length;
// Process each node in the current level
while (size > 0) {
const current = queue.shift(); // Remove the first element in queue
// If we've reached the target, return the steps taken
if (current === target) return steps;
// Generate all possible next moves and add to queue
const comb = generateComb(current);
for (const next of comb) {
if (!seen.has(next)) { // Only add unvisited nodes
queue.push(next); // Add new combination to queue
seen.add(next); // Mark new combination as visited
}
}
size--; // Decrement level size
}
steps++; // Move to the next level (increment moves)
}
// If BFS completes without finding target, return -1
return -1;
};
/**
* generateComb - Generates all possible next moves for a given lock state
* @param {string} input - Current lock state
* @return {string[]} - Returns all possible next moves
*/
var generateComb = function(input) {
const combinations = [];
// Loop through each of the four wheels
for (let i = 0; i < 4; i++) {
// Get the current digit of the wheel
const digit = parseInt(input[i]);
// Roll the digit up by one (wrap around from 9 to 0)
const up = input.slice(0, i) + ((digit + 1) % 10) + input.slice(i + 1);
combinations.push(up); // Add the new combination to the result array
// Roll the digit down by one (wrap around from 0 to 9)
const down = input.slice(0, i) + ((digit - 1 + 10) % 10) + input.slice(i + 1);
combinations.push(down); // Add the new combination to the result array
}
return combinations;
};
Detailed Code Explanation
- Main Function
openLock
:- The
seen
set stores all visited states to prevent revisiting deadends and previous combinations. - We initialize a
queue
to store each combination and mark “0000” as visited to prevent reprocessing. - The BFS loop processes nodes level by level, allowing us to find the shortest path to
target
.
- The
- Combination Generator
generateComb
:- For each digit in the 4-digit lock, we generate two new states: one by rolling the digit up and one by rolling it down.
- Each new combination is added to the result array, which is then returned to the BFS loop for further processing.
- Core Logic:
- BFS systematically expands from the start state, checking all possible next moves.
- The algorithm uses
steps
to count levels, ensuring that when we reachtarget
, it’s in the minimum moves. - If BFS finishes without finding
target
, we return -1, as it’s impossible to reach.
Example Walkthrough
Consider the case where deadends = ["0201","0101","0102","1212","2002"]
and target = "0202"
:
- Initial State: queue =
["0000"]
, steps =0
- First Level (step = 1): From “0000”, we expand to “1000”, “9000”, “0100”, “0900”… adding all valid moves to the queue.
- Subsequent Levels: We keep expanding outward, avoiding deadends and marking visited states.
- Final Steps: Eventually, we reach “0202” in the minimum moves and return the step count.
Conclusion
This problem is an excellent example of BFS’s utility in finding shortest paths. Key takeaways include:
- Using BFS: For shortest path problems where each move has equal weight, BFS provides an efficient approach.
- Tracking Visited States: By storing visited states, we avoid deadends and reduce redundant processing.
- Generating Moves: By iterating through each digit and generating moves, we simulate all possible paths from a given state.
By practicing with problems like this, you’ll improve your understanding of BFS and how to apply it to real-world scenarios!
简单易懂的TypeScript哈希表教程
简单易懂的TypeScript哈希表教程
用TypeScript写个哈希表——说白了就是“找东西利器”
哈希表这个东西呢,跟生活中找钥匙差不多。想象一下,你每次出门都乱丢钥匙,回家要用半小时才能找到它。如果有个哈希表,那你一秒就能知道钥匙放哪了。所以今天我们来用TypeScript写个哈希表,别担心,跟朋友聊天一样简单。
什么是哈希表?
哈希表就像给你的钥匙分配了个专属抽屉,你把钥匙往哈希表里一丢,它自己找个抽屉放好,等你要用的时候,你直接问它:“我的钥匙在哪呢?” 它马上告诉你在哪个抽屉里,秒找。是不是很方便?那咱现在就来动手写一个。
代码部分——慢慢来,不急
我们来一步步写哈希表,代码都标注好,解释清楚,放心不会扯得太远。
class HashTable<T> {
// 创建一个桶数组,桶就是个小抽屉,里面装着key-value对
private buckets: Array<Array<[string, T]>>;
// 哈希表的大小,也就是有多少个抽屉
private size: number;
constructor(size: number) {
this.size = size;
// 创建一个指定大小的桶数组,初始每个位置是个空数组
this.buckets = new Array(size).fill(null).map(() => []);
// 为啥要fill(null)?TypeScript不允许你直接在空数组上map,得先填充一波。
}
// 哈希函数,负责把key变成数字,这样才能找到对应的桶
private hash(key: string): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
// 计算哈希值,用ASCII码+位置的算法,最后取模,得到抽屉位置
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash; // 这个数字就是抽屉的索引
}
// 插入或更新键值对
set(key: string, value: T): void {
const index = this.hash(key); // 通过哈希函数找到抽屉
const bucket = this.buckets[index]; // 拿到对应的抽屉
// 先看看抽屉里有没有相同的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
// 找到了,就更新value
pair[1] = value;
return;
}
}
// 没找到?那就直接把新的key-value对扔进去
bucket.push([key, value]);
}
// 查找键值对
get(key: string): T | undefined {
const index = this.hash(key); // 先找到抽屉
const bucket = this.buckets[index]; // 拿出这个抽屉
// 遍历抽屉里的东西,看看有没有这个key
for (const pair of bucket) {
if (pair[0] === key) {
return pair[1]; // 找到了,直接返回value
}
}
return undefined; // 没找到,给你个undefined,你懂的
}
// 删除键值对
remove(key: string): boolean {
const index = this.hash(key); // 一样先找到抽屉
const bucket = this.buckets[index]; // 取出这个抽屉
// 遍历抽屉,找到要删的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
bucket.splice(i, 1); // 找到后直接删掉
return true; // 成功删除,返回true
}
}
return false; // 没找到就返回false,删除失败
}
}
说点需要注意的
- 构造函数那点事儿
为啥得先fill(null)
?TypeScript不让直接在空数组上map()
,所以你得先用fill(null)
把它填满,再通过map()
每个位置给它创建一个空的抽屉。不这样搞,TypeScript就会给你脸色看(直接报错)。 - 哈希函数到底在干嘛?
你可能好奇这hash()
函数到底干啥。其实它就是把字符串变成一个数字,方便找到你想要的抽屉。这里我们用了每个字符的ASCII码乘以它在字符串里的位置,最后对哈希表的大小取模。简单、暴力、够用!但别想太复杂,咱写这个不是为了拿诺贝尔奖,能用就行。 - 冲突咋处理?
冲突是难免的,两个key
哈希到同一个位置就叫冲突。这里我们用了“链地址法”来处理冲突,简单来说就是一个桶可以存多个键值对,每次冲突时就往同一个桶里塞。不过,这种方式容易导致某些桶变得过于拥挤,性能就可能下降。如果你想避免这种情况,可以试试“开放地址法”(Open Addressing)。它的原理是,如果一个桶已经有数据了,哈希表会去找下一个空的桶来放新数据。总的来说,两种方法各有优缺点,你可以根据实际需求选择。 - 时间复杂度
哈希表的优势是大多数操作都是 O(1) 时间复杂度,也就是速度快!不过当冲突多了,桶里东西多了,链地址法会退化成 O(n),查找变得慢。所以,哈希表适合用在冲突不太多的场景,或者你可以用更复杂的数据结构,比如平衡二叉树来处理冲突,提升查找效率。
然后呢?
好了,你已经有了一个能插入、查找、删除数据的哈希表了。接下来如果你想进一步优化,我们可以聊聊其他的冲突处理方式,比如“开放地址法”——这玩意儿可以让你别再往一个抽屉里塞太多东西。另外呢,像红黑树这种高级结构,也可以用来提升性能,后面有机会我们再详细聊。
Implementing a Priority Queue in TypeScript: A Step-by-Step Guide
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.
Introduction
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.
Why TypeScript?
TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.
Step 1: Define the Priority Queue Class
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) {}
}
- heap: An array representing the binary heap.
- comparator: A function to compare two elements, defining the priority.
Step 2: Implement the Helper Methods
Swap Method
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]];
}
Parent and Child Index Methods
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;
}
Step 3: Implement the Push Method
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();
}
Heapify Up
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);
}
}
Step 4: Implement the Pop Method
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;
}
Heapify Down
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;
}
}
Step 5: Implement Peek and Size Methods
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;
}
Step 6: Implement the Update Method
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.
Update by Index
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.
Update by Value
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.
Remove and Remove By Index
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);
}
}
}
Step 7: Implement the Heapify Function
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);
}
}
Step 8: Use the Priority Queue to Solve LeetCode 215
Now, let’s use our PriorityQueue
to find the Kth largest element in an array.
Problem Statement
Given an integer array nums
and an integer k
, return the kth
largest element in the array.
Solution
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);
}
}
}
Testing the Solution
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
Testing the Update and Heapify Methods
Using heapify()
to Build a Heap from an Array
typescriptCopy 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
Rewriting the 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;
}
Why Use 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.
Reasons:
- Higher Efficiency:
- Lower Time Complexity: Using
heapifyDown()
, the overall time complexity of building the heap is O(n). If we were to useheapifyUp()
, the time complexity would increase to O(n log n) in the worst case. - Fewer Node Movements:
heapifyDown()
can fix all violations of the heap property from the current node down to the leaves in one pass, whereasheapifyUp()
might require multiple passes for each node.
- Lower Time Complexity: Using
- Suitable for Building the Entire Heap:
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.
Detailed Explanation
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);
}
}
- Calculating the Starting Index:
Math.floor(this.heap.length / 2) - 1
- This formula gives us the index of the last non-leaf node.
- In a binary heap, nodes with indices from
Math.floor(n/2)
ton - 1
are all leaf nodes.
- Why Not Use
heapifyUp()
?heapifyUp()
is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.- Using
heapifyUp()
during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels. - In contrast,
heapifyDown()
can adjust the subtree rooted at a node in one pass.
An Example
Suppose we have an array [3, 2, 1, 5, 6, 4]
and we want to build a min-heap.
- Initialize the Heap:typescriptCopy code
this.heap = [3, 2, 1, 5, 6, 4];
- Start from the Last Non-Leaf Node:
- The array length is 6, so the index of the last non-leaf node is
Math.floor(6 / 2) - 1 = 2
.
- The array length is 6, so the index of the last non-leaf node is
- Perform
heapifyDown()
on Index 2:- The node at index 2 has a value
1
, and its children are out of bounds, so no action is needed.
- The node at index 2 has a value
- Perform
heapifyDown()
on Index 1:- The node at index 1 has a value
2
, with left child5
and right child6
. - Since
2
is less than its children, no action is needed.
- The node at index 1 has a value
- Perform
heapifyDown()
on Index 0:- The node at index 0 has a value
3
, with left child2
and right child1
.The right child1
is the smallest, so we swap3
with1
.
- The heap now looks like
[1, 2, 3, 5, 6, 4]
.
- The node at index 0 has a value
- Continue
heapifyDown()
on the Swapped Node:- The node at index 2 (now with value
3
) has a left child4
, but since3
is less than4
, no further action is needed.
- The node at index 2 (now with value
Summary
- Using
heapifyDown()
:- Ideal for building a heap from an array.
- Overall time complexity is O(n).
- Using
heapifyUp()
:- Suitable for inserting a single element into an existing heap.
- Each insertion has a time complexity of O(log n).
Therefore, in the heapify()
method, we choose heapifyDown()
to efficiently build a valid heap from the bottom up.
Additional Notes
- Why Not Use
heapifyUp()
?- If we used
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.
- If we used
- Time Complexity Comparison:
- Using
heapifyDown()
: Total time complexity is O(n). - Using
heapifyUp()
: Total time complexity is O(n log n).
- Using
Conclusion
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.