Record 1 algorithm problem
The KTH largest element in the data stream
Leetcode-cn.com/problems/kt…
Hopefully, I can clarify the heap and how the heap is optimized.
- Let’s start with the more direct approach.
You can maintain an array of the first k elements, bubble each time you add them, put the new ones in the right place, and then pop the smallest ones into the array.
function KthLargest(k, nums) {
this.k = k
this.data = []
for (let i = 0; i < nums.length; i++) {
this.add(nums[i])
}
}
KthLargest.prototype.add = function (val) {
const data = this.data
// If there are not enough k, just push ahead and sort
if (data.length < this.k) {
data.push(val)
} else if (val > data[data.length - 1]) {
// If enough, replace the smallest one and bubble
data[data.length - 1] = val
}
let a = data.length - 1
// From the end of the bubble forward, each push will sort, so just stop to finish
// The entire data is in descending order
while (data[a] > data[a - 1]) {
const temp = data[a]
data[a] = data[a - 1]
data[a - 1] = temp
a--
}
return data[data.length - 1]}Copy the codeAlthough it has been optimized to only need to sort K, but the performance of execution time is still poor.
Things like this can be done with a heap. The KTH is the smallest heap, the KTH is the largest heap. The minimum heap and maximum heap are just ascending or descending when sorting. It actually means pile already.
- Then the second point of optimization is to introduce a flat array version of the search binary tree. Let’s start with the array version implementation.
[A, b, C, D, E, F, G, H, I,j, K, L, m] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Or be someone else's child node. a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12Copy the codeThe flat array is actually created by pushing through the array one layer at a time, just like sequential traversal. The subscript of a binary tree is, let’s say, an arithmetic sequence.
I 2n* I +1 2n* I +2 Parent left right parent subscript left subscript right subscript A B C 0 12 B D E 1 3 4 C F G 2 5 6 d H I 3 7 8 E j k 4 9 10 F L M 5 11 12Copy the codeThis rule is satisfied when we know the subscript of the parent node. But if you know that the left and right child nodes push back the parent node, you can’t use the above rule. We can use I >> 1, take the middle index. Same as math.floor (I /2). However, it should be noted that the calculated result is offset by 1 bit, and the solution is (i-1) >> 1. Subscript minus 1.
a b c d e f
0 1 2 3 4 5Normally, when calculating the parent node from the child node, it should be a group of A, B and C. But I > >1So we have b, C, and D1.2 >> 1 , 3 >> 1. So the first -1That's right. a b c0, (2-1) > >1, (3-1) > >1
Copy the codeThe reason for introducing binary trees is to optimize the calculation, we just need to know what the KTH largest element is, not how the k minus 1 elements are sorted. Even if it’s 9, 10, 7, 5, it doesn’t matter that the fourth element is 5.
The root node at the top of a binary tree is the KTH largest element, and its children are always bigger than their parents because of the ascending order. It’s in ascending order in an array.
But you might get confused about how a binary tree compares the left node to the right node, how it bubbles. How is it optimized?
The next section uses code and examples to explain why binary trees work.
We first initialize a heap and then add data to the heap. I’m also using add.
function KthLargest(k, nums) {
this.k = k
this.heap = new Heap()
for (let i = 0; i < nums.length; i++) {
this.add(nums[i])
}
}
KthLargest.prototype.add = function (val) {
const { heap } = this
heap.push(val) /* When the ascending order is finished, the push will bubble */
if (heap.size() > this.k) {
heap.pop() /* Overwrite the smallest number with the last one, and bubble */
}
return heap.data[0] // The first one is the KTH largest number.
}
Copy the codeNext comes the key heap constructor
// Do some infrastructure first
class Heap {
constructor() {
// Ascending array
this.data = []
this.compare = (a, b) = > a - b
}
size() {
return this.data.length
}
swap(n1, n2) {
const { data } = this
const temp = data[n1]
data[n1] = data[n2]
data[n2] = temp
}
// Push into the heap
push(val) {}
// Add a new number instead of the KTH largest
pop() {}
// Bubble up from index, usually the end of the array
bubblingUp(index) {}
// Sink from index, usually at the beginning of an array
bubblingDown(index){}}Copy the codeWhen you bubble up, the regular version is a bubble that compares one by one, and when you introduce a binary tree, you compare the parent node, not one by one, and you reduce the comparison by at least half.
Is it possible to miss just comparing to the parent node? The answer is no. The characteristic of this tree is that the value of the right node is larger than the value of the left node, and the left and right children are larger than their parents.
Because of the ascending order, as long as the bubble is smaller than the parent node, it must be smaller than another child node.
Take [9, 10, 7, 5] for example. Use the relationship between parent and child subscripts analyzed above. Bubbling up is to find the parent node’s subscript based on the child node’s subscript. Subtracting is to find the subscripts of the children according to the subscripts of the parents.
bubblingUp(index) {
const { data } = this
// Only two or more bubbles are required
while(index > 0) {
const parent = (index - 1) > >1
// As with the sort rule, -1 is swapped
if (this.compare(data[index], data[parent]) < 0) {
this.swap(index, parent)
// Keep bubbling
index = parent
} else {
// Because it is in ascending order, it can be stopped prematurely.
break}}}Copy the codeWhen there is one in the array [9], push 10. Subscript of child node: 1, subscript of parent node: (1-1) >> 1 = 0, compare data[0] and data[1]. No bubbles.
[9, 10], push 7. Calculate the subscript of the child node: 2, and the subscript of the parent node: (2-1) >> 1 = 0, and compare data[2] and data[0]. Student: Exchange. New child node subscript 0, end bubbling
[7, 10, 9] push 5. Calculate subscript of child node: 3, coordinate of parent node: (3-1) >> 1 = 1, compare data[3] and data[1]. Student: Exchange. New child node subscript 1, continue to bubble
[7, 5, 9, 10], then the subscript of the child node is 1, and the bubbling of 5 continues. The subscript of the parent node is 0
The final binary tree is 1, 2
[5, 7, 9, 10]Copy the codeAnd then each parent is compared to the left and right nodes as it sinks. This comparison confirms that in every parent-child relationship, the right node is larger than the left node. Then make sure to replace the parent node with the smallest one in the left and right nodes as you sink
bubblingDown(index) {
const { data } = this
while(true) {
const left = index * 2 + 1
const right = index * 2 + 2
let parent = index
// Compare the left node with the parent node, the left node is compared first, so the right node will be larger than the left node
if (this.compare(data[left], data[parent]) < 0) {
parent = left
}
// If the left node is smaller than the parent node, parent = left to compare the left and right nodes.
// If the right node is smaller than the left node, then parent = right.
// If the right node is larger than the left node, the parent node swaps with the left node.
// If the branch of the upper left node does not enter, the left node is larger than the parent node,
// Compare the size of the right node with that of the parent node.
if (this.compare(data[right], data[parent]) < 0) {
parent = right
}
if(index ! == parent) {// Swap when comparing
this.swap(index, parent)
index = parent
} else {
// End the loop when there is no need to swap, otherwise the loop is dead, because the index does not change
break}}}Copy the codePush and pop are easy, just refer to the bubbling and sinking methods.
push(val) {
this.data.push(val)
// The index of the number just pushed
this.bubblingUp(this.size() - 1)}pop() {
if (this.size() === 0) return
const { data } = this
// The KTH largest number
const discard = data[0]
// The largest number
const newMember = data[pop]
Discard (newMember) discard (newMember) discard (newMember) discard (newMember)
if (this.size() > 0) {
data[0] = newMember
this.bubblingDown(0)}return discard // Thoughtful returns the once KTH element that was kicked out
}
Copy the codeThe above is JavaScript simulation heap optimization code, I hope to clarify.
Here’s the full code for the problem.
function KthLargest(k, nums) {
this.k = k
this.heap = new Heap()
for (let i = 0; i < nums.length; i++) {
this.add(nums[i])
}
}
KthLargest.prototype.add = function (val) {
const { heap } = this
heap.push(val) /* * * */
if (heap.size() > this.k) {
heap.pop() /* Overwrite the smallest number and sort */
}
return heap.data[0]}class Heap {
constructor() {
this.data = []
this.compare = (a, b) = > a - b
}
size() {
return this.data.length
}
swap(n1, n2) {
const { data } = this
const temp = data[n1]
data[n1] = data[n2]
data[n2] = temp
}
push(val) {
this.data.push(val)
this.bubblingUp(this.size() - 1)}pop() {
if (this.size() === 0) return null
const { data } = this
const discard = data[0]
const newMember = data.pop()
if (this.size() > 0) {
data[0] = newMember
this.bubblingDown(0)}return discard /* The smallest node in the heap that was kicked */
}
bubblingUp(index) {
/ * bubble, the minimum risk to the first, is the father-son relationship according to the binary tree, fully ascending * /
while (index > 0) {
/* Layer by layer will finally focus to 0 */
/* subtracts by 1 to match the parent node */ of the binary tree
const parent = (index - 1) > >1
const { data } = this
if (this.compare(data[index], data[parent]) < 0) {
this.swap(parent, index)
index = parent
} else {
break}}}bubblingDown(index) {
/* Transpose the largest number of nodes to the subscript of the leaf node according to the distribution of the binary tree, not completely ascending */
const { data } = this
const last = this.size() - 1
while (true) {
/* The reason to use a binary tree and not guarantee the ascending order is that as long as the KTH is large, you don't care about the order, the root of the binary tree is the KTH largest number */
const left = index * 2 + 1
const right = index * 2 + 2
let parent = index
if (left <= last && this.compare(data[left], data[parent]) < 0) {
parent = left
}
/* The smaller of the left and right child nodes is squeezed up */
if (right <= last && this.compare(data[right], data[parent]) < 0) {
parent = right
}
if(index ! == parent) {this.swap(index, parent)
index = parent
} else {
break}}}}Copy the code