Series article guide
- Kiner algorithm brush topic (a) : linked list and linked list ideas
- Kiner algorithm: Recursion and stack (solve the expression evaluation problem)
- Kiner algorithm brush topic (3) : thread pool and task queue
- Do you really know binary trees?
- Do you really know binary trees?
- Kiner algorithm: Heap and Priority queue
- Kiner algorithm brush topic (five) : Heap (priority queue)
The open source project
All articles in this series will be collected and managed in GitHub. Welcome ISSUE and Star.
GitHub portal: Kiner algorithm
preface
In our last article, we talked about the concept and properties of heap. I believe that you have a preliminary understanding of the data structure like heap. In order to deepen your understanding and familiarize yourself with the application scenarios of heap, I will take you to brush some algorithm problems to deepen your memory. Start with Heap and priority queues (Basics of Data Structures).
PS: their thinking is not necessarily the following algorithm to solve the optimal algorithm of train of thought, however, in order to consolidate the understanding of the use and characteristics of pile, all of us are achieved through the method of the heap, some topic do not use the heap, using other methods may be more efficient to complete the task, the classmate of your own thinking.
LeetCode refers to Offer 40.The smallest number of k
Their thinking
How do we use the heap to solve this problem? We said that the heap is suitable for maintaining maxima in sets, and we should use a big top heap to compare maxima in sets in real time. So let’s say that we have a set of length K, and we have all the numbers that we want to put in the set, and if the set is less than or equal to k, then we just add it, If length is greater than k, then we will compare the value of the entrance to the end than the maximum of a set of big or small, if is greater than the value of a set of, this is not what we want, put it to remove oil from the collection, if is smaller than the maximum value, then the value should be added to the collection, but because we as long as the number of k, So you have to pop the maximum out.
PS: Heap implementation is explained in detail in the last article, so I will not repeat it here. If there is any confusion, you can take a look at the last article
Code demo
// The implementation of the big top heap was explained in detail in the previous article, so it will not be repeated here. If there is any confusion, please refer to the previous article
class Heap {
private count: number = 0;
private arr: number[] = [];
constructor(){}
_shiftUp(idx: number) :void {
while(idx && this.arr[parseInt(String((idx - 1) / 2))] < this.arr[idx]) {
const pIdx = parseInt(String((idx - 1) / 2));
[this.arr[idx], this.arr[pIdx]] = [this.arr[pIdx], this.arr[idx]];
idx = pIdx;
}
}
_shiftDown(idx: number) :void {
const n = this.count - 1;
while(2*idx+1<=n) {
let max = idx;
if(this.arr[max] < this.arr[2*idx+1]) max = 2*idx+1;
if(2*idx+2<=n && this.arr[max] < this.arr[2*idx+2]) max = 2*idx+2;
if(max === idx) break;
[this.arr[max], this.arr[idx]] = [this.arr[idx], this.arr[max]];
idx = max;
}
}
push(x: number) :void {
this.arr[this.count++] = x;
this._shiftUp(this.count - 1);
}
pop(): number {
if(!this.size()) return -1;
const tmp = this.arr[0];
this.arr[0] = this.arr[this.count-1];
this.count--;
this._shiftDown(0);
return tmp;
}
size(): number {
return this.count;
}
top(): number {
return this.arr[0];
}
getArray(): number[] {
// Since we have no real physical deletion, we need to intercept this.count elements when we retrieve the array of the actual heap
return this.arr.slice(0.this.count); }}function getLeastNumbers(arr: number[], k: number) :number[] {
const heap = new Heap();
arr.forEach(item= >{
// Add each element of the array to the heap
heap.push(item);
// If the heap size is greater than k, pop the maximum value
if(heap.size()>k) { heap.pop(); }});// At the end of the loop, the heap contains the KTH smallest array we want
return heap.getArray();
};
Copy the codeLeetCode 1046. The weight of the last stone
Their thinking
This problem is also obviously to set the value of the problem, we just need to put all the stones in large heap, if the heap of stones is greater than 1, the number of every time out of the largest stone crushing and large rocks, if have the rest of the will add to the pile, as at the end of the cycle, or in the heap is lost a stone, or only one, If only one is left, the weight of the stone is what we want
Code demo
/* * @lc app=leetcode.cn id=1046 lang=typescript * * [1046] Weight of the last stone */
// @lc code=start
class Heap {
private count: number = 0;
private arr: number[] = [];
constructor(){}
_shiftUp(idx: number) :void {
while(idx && this.arr[parseInt(String((idx - 1) / 2))] < this.arr[idx]) {
const pIdx = parseInt(String((idx - 1) / 2));
[this.arr[idx], this.arr[pIdx]] = [this.arr[pIdx], this.arr[idx]];
idx = pIdx;
}
}
_shiftDown(idx: number) :void {
const n = this.count - 1;
while(2*idx+1<=n) {
let max = idx;
if(this.arr[max] < this.arr[2*idx+1]) max = 2*idx+1;
if(2*idx+2<=n && this.arr[max] < this.arr[2*idx+2]) max = 2*idx+2;
if(max === idx) break;
[this.arr[max], this.arr[idx]] = [this.arr[idx], this.arr[max]];
idx = max;
}
}
push(x: number) :void {
this.arr[this.count++] = x;
this._shiftUp(this.count - 1);
}
pop(): number {
if(!this.size()) return -1;
const tmp = this.arr[0];
this.arr[0] = this.arr[this.count-1];
this.count--;
this._shiftDown(0);
return tmp;
}
size(): number {
return this.count;
}
top(): number {
return this.arr[0];
}
getArray(): number[] {
// Since we have no real physical deletion, we need to intercept this.count elements when we retrieve the array of the actual heap
return this.arr.slice(0.this.count); }}function lastStoneWeight(stones: number[]) :number {
const heap = new Heap();
// Put all the stones in the big top pile first
stones.forEach(stone= > heap.push(stone));
// If the number of stones in the heap is greater than 1
while(heap.size()>1) {
// Pop out the largest stone and the second largest stone
const s1 = heap.pop();
const s2 = heap.pop();
// If it is equal, nothing is done
if(s1 == s2) continue;
// Otherwise put the number of remaining stones back into the heap
heap.push(s1-s2);
}
// If there are no elements in the heap, return 0
if(heap.size()===0) return 0;
// Otherwise return the heaptop element
return heap.top();
};
// @lc code=end
Copy the codeLeetCode 703. The KTH largest element in the data stream
Their thinking
If we want to find the KTH largest number in a set, then at least the element we add to the set can’t be smaller than the smallest element in the set. So whenever we get full, we’re going to strip out the smallest element, so to compare minima, we’re going to use the small top heap this time
Code demo
/* * @lc app=leetcode.cn id=703 lang=typescript * * the KTH element in the [703] data stream */
// @lc code=start
// The following is a definition of a structure that allows us to quickly create a large or small top heap. If you don't understand this, you can refer to the previous article, which explained it in detail.
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(): void {
console.log(JSON.stringify(this.arr)); }}class KthLargest {
// If we want to find the KTH largest number in a set, then at least the element we add to the set cannot be smaller than the smallest element in the set
// So whenever the collection is full, we have to strip out the smallest element. To compare minima, we use the small top heap this time
private heap = new Heap<number> ((x,y) = >x.data>y.data);
private k: number;
constructor(k: number, nums: number[]) {
this.k = k;
// Push all the elements of the array into the heap
nums.forEach(num= > this.add(num));
}
add(val: number) :number {
this.heap.push({data: val});
// If the heap size exceeds k, pop the minimum value
if(this.heap.size()>this.k) {
this.heap.pop();
}
// Return the top element of the heap as the KTH value we want
return this.heap.top().data; }}/** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */
// @lc code=end
Copy the codeLeetCode 215. The KTH largest element in the array
Their thinking
We add each element in turn to the heap, and we see if the size of the heap exceeds K, and if it exceeds K, we pop out the minimum, and finally, the top element is what we want
Code demo
/* * @lc app=leetcode.cn id=215 lang=typescript * * the KTH largest element in the [215] array */
// @lc code=start
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(): void {
console.log(JSON.stringify(this.arr)); }}function findKthLargest(nums: number[], k: number) :number {
// instantiate a small top heap
const heap = new Heap<number> ((x,y) = > x.data>y.data);
nums.forEach(num= >{
heap.push({data: num});
if(heap.size()>k) { heap.pop(); }});return heap.top().data;
};
// @lc code=end
Copy the codeLeetCode 373. Find and the smallest k-pair number
Their thinking
According to the formula, minimum K… , then use the big top heap, need the maximum K… , then use the small top heap, so build a big top heap, the big top heap is stored in an array of numeric type, if you want to and minimum, calculate and, and then according to: the big top heap with less than, small top heap with greater elements directly judge.
Then make a two-element array out of the two arrays and put it in the heap. When it’s full, pop up the largest element
Code demo
/* * @lc app=leetcode.cn id=373 lang=typescript * * [373] Find and min K pairs of digits */
// @lc code=start
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
// this.output('push: ');
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
// this.output('pop: ');
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(pre: string = "") :void {
console.log(pre+JSON.stringify(this.arr));
}
// Separate the data from the heap into an array
getArray(): T[] {
return this.arr.slice(0.this.count).map(item= >item.data); }}function kSmallestPairs(nums1: number[], nums2: number[], k: number) :number[] []{
// Minimum k... , then use the big top heap, need the maximum K... , then use the small top heap, so
// Create a small top heap. The big top heap contains an array of numeric types.
// The big heap uses less than, and the small heap uses greater
const cmp = (x, y) = > x.data[0] + x.data[1] < y.data[0] + y.data[1];
const heap = new Heap<number[]>(cmp);
nums1.forEach(num1= > {
nums2.forEach(num2= > {
const top = heap.top();
If the size of the heap is less than k and the data we want to add is smaller than the top element of the heap, otherwise we jump out of the current loop
// Why jump out of the loop? Nums1 and nums2 are ordered arrays. If the sum of the current num2 and num1 is greater than the sum of the top elements,
// If nums2 is added to nums1, there is no need to compare the result. Therefore, for performance reasons, if this happens, we can jump out of nums2 loop.
// Continue into the next nums1 loop
if(heap.size() < k || cmp({data: [num1, num2]}, top)) {
// Add data from both arrays to the heap
heap.push({
data: [num1, num2]
});
// If the heap size exceeds k, the maximum value is popped
if(heap.size()>k) heap.pop();
} else {
return false; }}); });// Finally, our heap contains the answers we need
return heap.getArray();
};
// @lc code=end
Copy the codeLeetCode 692. The first K high-frequency words
Their thinking
The answer to this question is: First calculate the frequency of each word, because we want to calculate the frequency up to k, see “how” we are going to think of using a small heap, therefore, we need to build a little heap, however, this problem is a special request, when two words appear frequency is same, need according to the word of the ASCII table sorting, therefore, When we define the comparison function of the small top heap and the final output array, we need to do a special treatment for this case. In js, String provides a very convenient according to ASCII String sort of auxiliary table method. The prototype. LocaleCompare () allows us to easily compare two String ASCII whoever playing small.
Code demo
/* * @lc app=leetcode.cn id=692 lang=typescript * * [692] */
// @lc code=start
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
// this.output('push: ');
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
// this.output('pop: ');
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(pre: string = "") :void {
console.log(pre+JSON.stringify(this.getArray()));
}
// Separate the data from the heap into an array
getArray(sort: (a: HeapDataStruct<T>, b: HeapDataStruct<T>) = > number = () = > 0): T[] {
return this.arr.slice(0.this.count).sort(sort).map(item= >item.data); }}function topKFrequent(words: string[], k: number) :string[] {
// Define a map to store the number of occurrences of each word. Key is the word and val is the number of occurrences
const map = {};
// Define the comparison rules for the small top heap
const cmp = (x,y) = > {
// If the frequency of the two words is different, because it is a small top heap, then the number of the current node should be greater than the number of the parent node
if(x.idx! ==y.idx)return x.idx>y.idx;
// If two words are equally frequent, we ascribe to them in descending order
return x.data<y.data;
};
// instantiate a small top heap
const heap = new Heap<string>(cmp);
// Count the occurrences of all words
words.forEach(word= >{
map[word]=(map[word]||0) +1;
});
Object.keys(map).forEach(key= >{
// Place each word and its corresponding number in the heap
heap.push({
idx: map[key],
data: key
});
// Pop up the minimum value when it is piled up
if(heap.size()>k) heap.pop();
});
/ / output is the result of the need to sort, in turn, the first is based on occurrences from big to small order, if the number is the same, is | | to the left of expression will be zero,
// Will enter the right-hand expression, which will compare the size of two strings based on local rules (ASCII)
return heap.getArray((a,b) = > {
return (b.idx - a.idx) || a.data.localeCompare(b.data);
});
};
// @lc code=end
Copy the codeLeetCode 295. The median of data streams
Their thinking
To do this, we need to use a structure called the opposite top heap, which is essentially a big top heap on the left and a small top heap on the right, and we can maintain the median of the set of two heaps by looking at the top elements of the big top heap and the small top heap.
Median chrysene ┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬ exponent ┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴ -- our r large top pile small top pile# As shown in the figure above, the top of the big heap and the top of the small heap are both on the dotted line side of the median. We try to keep the number of elements in the big heap and the small heap the same, but when the number of elements in the big heap is too large, we can move the top elements in the big heap to the small heap to make them as even as possible. Thus, when all of our trees are added to the two heaps, if the total number is odd, then the median is the top element of the larger heap of our two heaps, and if the total number is even, it is the average of the two top elements
Copy the codeCode demo
/* * @lc app=leetcode.cn id=295 lang=typescript * * [295] Median of data streams */
// @lc code=start
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
// this.output('push: ');
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
// this.output('pop: ');
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(pre: string = "") :void {
console.log(pre+JSON.stringify(this.getArray()));
}
// Separate the data from the heap into an array
getArray(sort: (a: HeapDataStruct<T>, b: HeapDataStruct<T>) = > number = () = > 0): T[] {
return this.arr.slice(0.this.count).sort(sort).map(item= >item.data); }}class MedianFinder {
private lHeap: Heap<number>;
private rHeap: Heap<number>;
constructor() {
// Maintain a large top heap on the left
this.lHeap = new Heap((x,y) = >x.data<y.data);
// Maintain a small top heap on the right side
this.rHeap = new Heap((x,y) = >x.data>y.data);
}
addNum(num: number) :void {
// We try to insert elements into the heap on the left
// Therefore, the left heap is inserted when the left heap is empty or the element to be inserted is less than or equal to the top element of the left heap
if(this.lHeap.size()===0 || num <= this.lHeap.top().data) {
this.lHeap.push({data: num});
} else {
this.rHeap.push({data: num});
}
// Adjust the number of elements in the left and right heaps so that the left heaps have at most one more element than the right heaps
this.transformHeap();
}
transformHeap(){
// We agree that the left heap can have at most one more element than the right heap
// When our total is odd, the top element of the heap on the left is the median we want
// When our total is even, the average of the top elements of the left and right heaps is the median we want
if(this.rHeap.size() > this.lHeap.size()) {
this.lHeap.push(this.rHeap.pop());
}
if(this.lHeap.size() === this.rHeap.size()+2) {
this.rHeap.push(this.lHeap.pop());
}
}
findMedian(): number {
// Because we try to insert elements into the left heap first, and there is at most one more element on the left than on the right, when the number of left heaps is greater than that on the right
// Return the top element of the left heap
if(this.lHeap.size()>this.rHeap.size()) {
return this.lHeap.top().data;
} else {// If it is even, we need to take the average of the left and right heaps
return (this.lHeap.top().data + this.rHeap.top().data) / 2; }}}/** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */
// @lc code=end
Copy the codeLeetCode Interview question 17.20. Median of continuity
Their thinking
This is exactly the same problem we solved in the last one, so I won’t repeat it here
LeetCode 264. The ugly number II
Their thinking
This problem is actually the key point is that, how do we avoid double counting of certain trees, which is to the pruning of the heap, actually we need only with a prime factors in only when the modulus is 0, only multiplied by itself and is greater than its prime factors, and for its smaller prime factors, before has been calculated, not repeated calculation.
Code demo
/* * @lc app=leetcode.cn id=264 lang=typescript * * [264] ugly number II */
// @lc code=start
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
// this.output('push: ');
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
// this.output('pop: ');
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(pre: string = "") :void {
console.log(pre+JSON.stringify(this.getArray()));
}
// Separate the data from the heap into an array
getArray(sort: (a: HeapDataStruct<T>, b: HeapDataStruct<T>) = > number = () = > 0): T[] {
return this.arr.slice(0.this.count).sort(sort).map(item= >item.data); }}function nthUglyNumber(n: number) :number {
// Define a small top heap
const heap = new Heap<number> ((x, y) = >x.data>y.data);
// Put the 1 in first
heap.push({data: 1});
let res;
while(n--) {
// Pop the top element of the heap as the result of this round
res = heap.pop();
// To avoid double counting, we can prune our heap
// Only when modulo is 0 with a prime factor, multiply by itself and prime factors larger than it
if(res.data % 5= = =0) {
heap.push({data: res.data * 5});
} else if(res.data % 3= = =0) {
heap.push({data: res.data * 5});
heap.push({data: res.data * 3});
} else {
heap.push({data: res.data * 5});
heap.push({data: res.data * 3});
heap.push({data: res.data * 2}); }}// After n rounds of traversal, the final result is the ugly number we want
return res.data;
};
// @lc code=end
Copy the codeLeetCode 1801. Total number of orders in backlog
Their thinking
For this problem, we definitely want our purchase order amount to be as large as possible, so we need to maintain the maximum value and use the large top heap, while sales order amount should be as small as possible, so as to earn more price difference, so we need to maintain the minimum value and use the small top heap.
Code demo
export typeHeapDataStruct<T> = { idx? :number.data: T
};
export type CompareFn<T> = (x: HeapDataStruct<T>, y: HeapDataStruct<T>) = > boolean;
class Heap<T> {
private arr: HeapDataStruct<T>[] = [];
private count: number = 0;
constructor(private cmpFn: CompareFn<T>){}private _compare(curIdx: number.pIdx: number) :boolean {
return this.cmpFn(this.arr[curIdx], this.arr[pIdx])
}
private _shift_up(idx: number) :void {
// Then adjust the heap upward
// We need the coordinates of the parent node from the child node, because our subscript starts from 0, so the left child root node coordinates are: 2 * I + 1, and the right child root node coordinates are: 2 * I + 2. ParseInt ((2 * I + 1-1) / 2) = parseInt(I); parseInt((I + 1-1) / 2) = parseInt(I); ParseInt ((2* I + 2-1)/2) = parseInt((2* I +1)/2) = I
// As we said above, we need to swap the two values if the parent is less than the child in a big top heap
// while(idx && this.arr[parseInt(String((idx - 1) / 2))].data < this.arr[idx].data) {
while(idx && this._compare(parseInt(String((idx - 1) / 2)), idx)) {
// Number of the parent node
const pIdx = parseInt(String((idx - 1) / 2));
// Swap the parent node and the current node
[ this.arr[pIdx], this.arr[idx] ] = [ this.arr[idx], this.arr[pIdx] ];
// Then change the idx to the number of the parent node, so that it can be adjusted upwardidx = pIdx; }}private _shift_down(idx: number) :void {
// After the swap, the root node is adjusted down in turn
// The subscript of the largest child node
let n = this.count - 1;
// If the subscript of the idX child node is smaller than the subscript of the largest child node, it indicates that there are children
while(idx * 2 + 1 <= n) {
// Max represents the subscript of the maximum value in the root node, left subtree, and right subtree
let max = idx;
If the value of the root node of the left subtree is greater than the current value, update Max to the subscript of the left child root node
// if(this.arr[max].data < this.arr[2*idx+1].data) max = 2*idx+1;
if(this._compare(max, 2*idx+1)) max = 2*idx+1;
If the value of the right child root node is greater than the current node, update Max to the subscript of the right child root node
*idx+2<=n *idx+2<=n *idx+2<=n
if(2*idx+2<=n && this._compare(max, 2*idx+2)) max = 2*idx+2;
// if(2*idx+2<=n && this.arr[max].data < this.arr[2*idx+2].data) max = 2*idx+2;
// If the index of my maximum value is the current value, I don't need to adjust it down, and just end the loop
if(max === idx) break;
// Then swap the subscript and root of the maximum value
[ this.arr[idx], this.arr[max] ] = [ this.arr[max], this.arr[idx] ];
// Then change idx to the subscript of the original maximum value and continue to adjust downward
idx = max;
}
}
push(item: HeapDataStruct<T>): void {
this.arr[this.count++] = item;
this._shift_up(this.count-1);
// this.output('push: ');
}
pop(): HeapDataStruct<T>|null {
if(this.size()===0) return null;
const tmp = this.arr[0];
// As explained above, we first need to swap the end of the queue with the root node
[ this.arr[0].this.arr[this.count-1]] = [this.arr[this.count-1].this.arr[0]].// Remember to decrease count by 1 after the swap
this.count--;
// Make a downward adjustment
this._shift_down(0);
// this.output('pop: ');
return tmp;
}
size(): number {
return this.count;
}
top(): HeapDataStruct<T> {
return this.arr[0];
}
output(pre: string = "") :void {
console.log(pre+JSON.stringify(this.getArray()));
}
// Separate the data from the heap into an array
getArray(sort: (a: HeapDataStruct<T>, b: HeapDataStruct<T>) = > number = () = > 0): T[] {
return this.arr.slice(0.this.count).sort(sort).map(item= >item.data); }}function getNumberOfBacklogOrders(orders: number[] []) :number {
// Store the purchase order with the big top heap
const buyHeap = new Heap<number[] > ((x, y) = > x.data[0]<y.data[0]);
// Use small top heap to store sales orders
const sellHeap = new Heap<number[] > ((x, y) = > x.data[0]>y.data[0]);
// Iterate through all orders
orders.forEach(order= > {
if(order[2= = =0) {// Purchase order
// 1. The quantity of purchase order is not 0
// 2. The number of sales orders is not 0
// 3. The amount of the purchase order should be greater than or equal to that of the sales order
while(order[1] && sellHeap.size() && order[0] >= sellHeap.top().data[0]) {
// We need to consider the number of sales orders and purchase orders. We should take the minimum value from these two orders as the number of orders to operate this time
const count = Math.min(order[1], sellHeap.top().data[1]);
// Once you know the number of orders to operate, subtract it from both the purchase order and the sales order
order[1] -= count;
sellHeap.top().data[1] -= count;
// At this point, if our sales order quantity is 0, we pop the order from the heap
if(sellHeap.top().data[1= = =0) sellHeap.pop();
}
// If, after a cycle, our current order order still has a surplus, it indicates that there is a backlog of orders, and we put the backlog into the purchase order
order[1]! = =0 && buyHeap.push({data: order});
} else {// Sales order
while(order[1] && buyHeap.size() && order[0] <= buyHeap.top().data[0]) {
const count = Math.min(order[1], buyHeap.top().data[1]);
order[1] -= count;
buyHeap.top().data[1] -= count;
if(buyHeap.top().data[1= = =0) buyHeap.pop();
}
order[1]! = =0 && sellHeap.push({data: order}); }});let res = 0;
// According to the problem, the value may be too large, we need to model the order quantity and mod
const mod = 1000000007;
// Get the heap array data
const buyArray = buyHeap.getArray();
// Get the sales heap in array format
const sellArray = sellHeap.getArray();
// Add total orders to res
buyArray.forEach(order= > {
res += (res + order[1]) % mod;
});
sellArray.forEach(order= > {
res += (res + order[1]) % mod;
});
return res;
};
Copy the code