The preface
Recently, I came across an object named “Big root Heap” in Leetcode. Firstly, I am not quite sure what it is, so I cannot change the exact definition. It’s a method, right? Or a ladder idea? Or a data structure? Or something else. Because this name appears in all kinds of problems. Such as:
- 215. The KTH largest element in an array
- Interview question 17.20. Median of continuity
- 295. The median of data streams
- .
Since so many questions appear [big root pile], it should be very important, and I will not; So I decided to figure it out
The heap
A heap is usually an array object that can be viewed as a complete binary tree
Example: array array = [7,3,8,5,1,2]
Array array can be thought of as a complete binary tree
7
/ \
3 8
/ \ /
5 1 2
Copy the codeDo you want to convert an array into a binary tree? No, no, no, just think of an array as a binary tree, or if I say 8 and 7 switch places, you say why switch places?
What is a big root heap?
What is a large root heap: each node has a value greater than or equal to the value of its left and right children. For example: array = [7,3,8,5,1,2
1/2/3 1/2Copy the codeIs the value of each node in the binary tree greater than or equal to the left and right child nodes?
This is the big root pile;
Question: You are still converting an array to a binary tree. No, the array changed from [7,3,8,5,1,2] to [8,5,7,3,1,2]
The array is still an array, but the values in the array have changed;
The changed rule is based on the large root heap rule of binary tree; So when you add or delete elements, you can quickly find the maximum and minimum value in the array
Conclusion: To find the best value, use large root heap, small root heap
How do you build a big root heap?
add
For example, array = [7,3,8,5,1,2], binary root bit 0; After construction, the big root heap bit list = [0], where 0 has no practical significance and represents the root node
1. Put the first digit of the array 7 into the binary tree
7
Copy the codeList = [0,7];
- List =,7,3 [0]
- Does list fit the big root heap?
7/3Copy the codeSelect * from array (‘ array ‘, ‘array’, ‘8’);
- List =,7,3,8 [0]
- Does list fit the big root heap?
7
/ \
3 8
Copy the codeNo, 8 is bigger than 7 so 8 has to switch places with 7;
It’s easier to see in a binary tree view, but how do you swap them in an application?
A few concepts need to be added here;
In a complete binary tree, for all non-root nodes x
The subscript of the parent value in array is: math.floor (x/2). The subscript of the left child value in array is: 2x. The subscript of the right child value in array is: 2x + 1
1
/ \
2 3
/ \ / \
4 5 6 7
Copy the codeSo, the 7 and 8 swap places with 8 at subscript 3 and with 7 at subscript 1, so the array becomes 0,8,3,7 and intuitively the binary tree becomes
8
/ \
3 7
Copy the codeSelect * from array (‘ array ‘, ‘5’)
- List =,8,3,7,5 [0]
8 / \ 3 7/5Copy the code- Does not meet the large root heap condition because 5 > 3
How do you adjust an array? Swap 5 with 3; What’s the subscript of 5? Is 4; The subscript of 3 can be calculated to be 2; So if you swap 5 with 3 you get list = [0,8,5,7,3]
8 / \ 5 7/3Copy the codeconclusion
Through the above four steps, you can know that when adding data to the array, it is now added to the end of the array, the end of the array represents the array leaf node; After the data is placed on the leaf node, the value is compared with the value of the parent node of the value. If the value is greater than the value of the parent node, the two positions are switched. Refer to Steps 3 and 4
Since the value is swapped upward from the leaf node, it is also the value of the parent node. After the swapped parent node is compared with the parent node, it is judged that the swapped parent node is compared to the root node or less than the parent node.
delete
Now list = [0,8,5,7,3]
8 / \ 5 7/3Copy the codeReturn array[1].
How about deleting the maximum value of the array?
First: the value of the last node and the first node switch; List = [0,3,5,7,8]
3 / \ 5 7/8Copy the codeStep 2: Delete the leaf node; List. The pop () list = hc-positie [0]
3
/ \
5 7
Copy the codeStep 3: Rebuild the large root heap
In this case, should the 3 be swapped with the left child or should it be swapped with the right child? This is the key;
Let’s say that 3 is swapped with the left child
5
/ \
3 7
Copy the codeNo, it’s still not a big root heap, because 7 is greater than 5, and if you swap 3 with the right child, you swap
7
/ \
5 3
Copy the codeAccord with large root heap;
Through the above two assumptions, we can reach a conclusion that if the root node can be swapped with its child node, the large root heap can be reconstructed, and then it can be swapped with the child node
With that in mind, you can edit the code
Write a heap
Put up a shelf first
class Heap {
constructor(compare) {
this.list = [0] // Array to store data
this.compare =
typeof compare === 'function' ? compare : this.defaultCompare
}
// Control heap ascending or descending order
defaultCompare(a, b) {
return a > b
}
isEmpty() {} // Whether it is empty
getSize() {}// Array length
top() {}/ / Max
pop() {}// Delete the maximum value
push() {}/ / add value
left = (x) = > 2 * x // Get the subscript of the left child node of the node based on the current node subscript
right = (x) = > 2 * x + 1
parent = (x) = > Math.floor(x / 2)}Copy the codeisEmpty
isEmpty() {
return this.num === 0
}
Copy the codetop
top() {
return this.list[1]}Copy the codepush
push(val) {
// Add data to the heap end
this.list.push(val)
this.up(this.list.length - 1)}/ / to rise
up(k) {
const { list, parent, compare } = this
// Iterates between the current node and the parent node
while (k > 1 && compare(list[k], list[parent(k)])) {
this.swap(parent(k), k)
k = parent(k)
}
}
Copy the codepop
Core code, key and difficult points, need to focus on understanding down function; From the first is, the data [sink] to the corresponding position,
pop() {
const { list } = this
if (list.length === 0) return null
this.swap(1, list.length - 1)
const top = list.pop()
this.down(1)
return top
}
down(k) {
const { list, left, right, compare } = this
const size = this.getSize()
console.log('size', size)
while (left(k) <= size) {
let _left = left(k)
if (right(k) <= size && compare(list[right(k)], list[_left])) {
_left = right(k)
}
if (compare(list[k], list[_left])) return
this.swap(k, _left)
k = _left
}
}
Copy the codeThe complete code
class Heap {
constructor(compare) {
this.list = [0]
this.compare =
typeof compare === 'function' ? compare : this.defaultCompare
}
defaultCompare(a, b) {
return a > b
}
swap(x, y) {
const t = this.list[x]
this.list[x] = this.list[y]
this.list[y] = t
}
isEmpty() {
return this.list.length === 1
}
getSize() {
return this.list.length - 1
}
top() {
return this.list[1]}left(x) {
return 2 * x
}
right(x) {
return 2 * x + 1
}
parent(x) {
return Math.floor(x / 2)}push(val) {
// Add data to the heap end
this.list.push(val)
this.up(this.list.length - 1)}/ / to rise
up(k) {
const { list, parent, compare } = this
while (k > 1 && compare(list[k], list[parent(k)])) {
this.swap(parent(k), k)
k = parent(k)
}
}
pop() {
const { list } = this
if (list.length === 0) return null
this.swap(1, list.length - 1)
const top = list.pop()
this.down(1)
return top
}
down(k) {
const { list, left, right, compare } = this
const size = this.getSize()
while (left(k) <= size) {
let _left = left(k)
if (right(k) <= size && compare(list[right(k)], list[_left])) {
_left = right(k)
}
if (compare(list[k], list[_left])) return
this.swap(k, _left)
k = _left
}
}
}
Copy the codeReference documentation
Heap – Baidu Encyclopedia