Goal:
- Master minimum heap
- Master partial sort
Find the KTH largest number
[4,5,8,2…]
At this point, you might want to sort by array sort
const sortArr = arr.sort((a, b) = > b - a )
Copy the codeSo the KTH largest number is sortArr[k-1]
But if you have 10 million numbers that are out of order, obviously when you have a lot of data you’re not going to be able to sort them all.
For example, I want to find the best breakfast shop in Beijing, but there may be 100,000 breakfast shops in Beijing, or even 10 million. If there are 100,000 breakfast shops in Beijing, I want the second best breakfast shop. I don’t want the first one, I want the second best breakfast shop. Certainly can’t like the above from 10 to 100 thousand so all sort, that would take a lot of time!
At this time, relative to full sort, there is a method called partial sort, is very suitable, so what is partial sort?
Find these Numbers top K in large Numbers, the back of the small Numbers do not, that is to say as long as give top K Numbers do a sorting is ok, but don’t have to sort all, even though the top K number also need not all sorts, as long as the top K of the smallest, which is as long as the top K number make a minimum heap data structure, Just take the smallest number
Before we get to the minimum heap, we need to understand the following concepts:
Binary tree
It is the simplest and most important tree in which the degree of the nodes is not greater than 2.
Full binary tree
All nodes in each layer have a binary tree of two children except the last layer, which has no children.
From the point of view of shape, full binary tree is a triangle in appearance.
A binary tree is full if the number of levels is K and the total number of nodes is (2^ K)-1.
Complete binary tree
A binary tree of depth K with n nodes is numbered from top to bottom and from left to right. If the node numbered I (1sisn) is in the same position as the node numbered I in the full binary tree, the binary tree is called a complete binary tree.
Leaf nodes can only occur in the largest two layers.
If the top 11 node does not exist, then the whole tree is not a complete binary tree, it can be missing from the right, but not from the left. So even if 12 goes away, it’s still a completely binary tree.
Next, let’s move on to the next concept:
The minimum heap
Minimum heap is a sort of complete binary tree in which the data value of any non-terminal node is not greater than the value of its left and right children
Every subtree has a minimum root, and it’s a minimum heap without 14, but it’s not a minimum heap without 15, because it’s not a complete binary tree anymore.
Minimum heap data structure
In JS we can choose arrays as the data structure of the minimal heap
| An array of | 3 | 7 | 4 | 10 | 12 | 9 | 6 | 15 | 14 |
|---|---|---|---|---|---|---|---|---|---|
| The depth of the | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
| The array subscript | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Subscripts of child nodes are calculated according to the subscripts of parent nodes:
leftIndex = (parentIndex + 1) * 2 – 1
rightIndex = leftIndex + 1
Calculate the subscript of the parent node according to the subscript of the child node:
parentIndex = (childIndex – 1) >>> 1
Implement a minimum heap
class MinHeap {
constructor(data = []) {
/ / the minimum heap
this.data = data
}
// Calculate the length
size() {
return this.data.length
}
}
Copy the codeNode operations:
Get the minimum node heap[0]
If this.data is already the minimum heap, then this.data[0] is the minimum heap value
// Get the minimum heap value
peek() {
return this.size() === 0 ? null : this.data[0]}Copy the codeInsert elements
Insert element 5
To ensure that the original data structure remains intact, you can insert elements from the tail
- Since 5 is less than 12, 5 switches places with 12, adjusting 5 from the bottom up
- So 5 is less than 7, 5 and 7 switch places, keep going up
- If 5 > 3, stop the adjustment
Add elements to the smallest heap
// Add elements to the smallest heap
push(node) {
this.data.push(node)
// Adjust the position
this.siftUp(node, this.size() - 1)}Copy the codeAdjust the position
// Add elements to the smallest heap
push(node) {
this.data.push(node)
// Adjust the position
this.siftUp(node, this.size() - 1)}siftUp(node, i) {
let index = i
while(index > 0) {
// Subscript the parent node
const parentIndex = (index -1) > > >1 // bit operation is the same thing as dividing by 2
/ / the parent node
const parent = this.data[parentIndex]
// Whether to adjust the position accordingly
if(this.compare(node, parent) < 0) {
// Child < parent
this.swap(index, parentIndex)
// Adjust the node subscript
index = parentIndex
} else {
break}}}Copy the codeIt’s just a constant process of changing the index, and at the end of the adjustment the index has to be at least 0. According to the above formula, we can find the subscript and parent node of the parent node and then compare it with the current node to see whether the corresponding position adjustment is needed
Compare two elements
/ / to compare
compare(a, b) {
return a - b
}
Copy the codeIf compare is less than 0, then a is less than B. In addition, it is convenient to separate the comparison process into a function for later modification. For example, in the future, a and B will not be two numbers, but two objects, which can be easily modified a.ort – b.ort
Switching elements
// Swap the values of two variables
swap(index1, index2) {
// [a, b] = [b, a]
[this.data[index1], this.data[index2]] = [
this.data[index2],
this.data[index1]
]
}
Copy the codeRemove elements
- First take a heap [0]
- In order not to destroy the data structure, it is possible to pop the array and place the end element 14 in the heap[0], but this is no longer the minimum heap and needs to be adjusted down
- Adjust from the node at position 0 down, compare with the left and right nodes to find the smallest, such as switching with 4 first
- And then I switch with 6
- complete
Delete the minimum value of the minimum heap
// Delete the minimum value of the minimum heap
pop() {
if(this.size() === 0) {
return null
}
const first = this.data[0]
const last = this.data.pop()
// if(first ! == last) {
if(this.size() ! = =0) {
this.data[0] = last
// Adjust downward
this.siftDown(last, 0)}}siftDown(node, i) {
let index = i
const length = this.size()
const halfLength = length >>> 1
while(index < halfLength) {
const leftIndex = (index + 1) * 2 - 1
const rightIndex = leftIndex + 1
const left = this.data[leftIndex]
const right = this.data[rightIndex]
if(this.compare(left, node) < 0) {
// left < parent node
if( rightIndex < length && this.compare(right, left) < 0) {
// Right < left, right smallest
this.swap(rightIndex, index)
index = rightIndex
} else {
// right >= left
this.swap(leftIndex, index)
index = leftIndex
}
} else if(rightIndex < length && this.compare(right, node) < 0) {
// left > node, right < node
/ / right is minimal
this.swap(rightIndex, index)
index = rightIndex
} else {
// The root node is the smallest
break}}}Copy the codeRealize a force deduction
The KTH largest element in the data stream
Design a class that finds the KTH largest element in the data stream. Notice it’s the KTH largest element, not the KTH different element.
Please implement KthLargest class:
KthLargest(int k, int[] nums) uses the integer k and the integer stream nums to initialize the object. Int add(int val) Returns the KTH largest element in the current data stream after inserting val into the data stream nums.
Example:
Input: [" KthLargest ", "add", "add", "add", "add", "add"] [[3] [4, 5, 8, 2], [3], [5], [10], [9], [4]] output: KthLargest KthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8Copy the codeThe complete code
/ * * *@param {number} k
* @param {number[]} nums* /
var KthLargest = function (k, nums) {
this.k = k
this.heap = new MinHeap()
for (const node of nums) {
this.add(node)
}
}
/ * * *@param {number} val
* @return {number}* /
KthLargest.prototype.add = function (node) {
this.heap.push(node)
console.log('heap'.this.heap)
if(this.heap.size() > this.k) {
this.heap.pop()
}
return this.heap.peek()
}
class MinHeap {
constructor(data = []) {
/ / the minimum heap
this.data = data
}
// Calculate the length
size() {
return this.data.length
}
/ / to compare
compare(a, b) {
return a - b
}
// Swap the values of two variables
swap(index1, index2) {
// [a, b] = [b, a]; [this.data[index1], this.data[index2]] = [
this.data[index2],
this.data[index1],
]
}
// Get the minimum heap value
peek() {
return this.size() === 0 ? null : this.data[0]}// Add elements
push(node) {
this.data.push(node)
// Adjust the position
this.siftUp(node, this.size() - 1)}siftUp(node, i) {
let index = i
while (index > 0) {
const parentIndex = (index - 1) > > >1 / / divided by 2
const parent = this.data[parentIndex]
if (this.compare(node, parent) < 0) {
// Child < parent
this.swap(index, parentIndex)
index = parentIndex
} else {
break}}}// Delete the minimum value of the minimum heap
pop() {
if (this.size() === 0) {
return null
}
const first = this.data[0]
const last = this.data.pop()
// if(first ! == last) {
if (this.size() ! = =0) {
this.data[0] = last
// Adjust downward
this.siftDown(last, 0)}}siftDown(node, i) {
let index = i
const length = this.size()
const halfLength = length >>> 1
while (index < halfLength) {
const leftIndex = (index + 1) * 2 - 1
const rightIndex = leftIndex + 1
const left = this.data[leftIndex]
const right = this.data[rightIndex]
if (this.compare(left, node) < 0) {
// left < parent node
if (rightIndex < length && this.compare(right, left) < 0) {
// Right < left, right smallest
this.swap(rightIndex, index)
index = rightIndex
} else {
// right >= left
this.swap(leftIndex, index)
index = leftIndex
}
} else if (rightIndex < length && this.compare(right, node) < 0) {
// left > node, right < node
/ / right is minimal
this.swap(rightIndex, index)
index = rightIndex
} else {
// The root node is the smallest
break}}}}const kthLargest = new KthLargest(3[4.5.8.2])
Copy the code