Data structure and Algorithm of front-end Science (6) : four traversal methods of binary tree and its application

preface

The tree structure is the most important data structure in 2001, because by adjusting the storage order of nodes or the number of branches, the type of problem can be completely different. The heap introduced in this chapter is also a kind of binary tree, which is similar to the binary search tree, but changes the rules for storing values of nodes. It follows the rule that the priority of each parent node must be greater than or equal to that of the child node. This data structure can also be called priority queue.

What is a priority queue?

In the previous chapter, we introduced the ordinary queue, which is fixed from the end of the queue, from the first queue. If the scenario now requires that the highest priority element must be removed from the queue every time you exit, you might say, that’s easy, just walk through the queue to find the highest priority element and remove it from the queue. This can really meet the needs of the scene, but also can appear a problem, is the team efficiency is too low, if you are using arrays, find the highest priority elements need to be O (n) time, then the team the element array need to O (n) displacement of the operation, that is to say, every time the team takes O (n squared) time, this is a bit too extravagant.

The pile of the array structure is designed to solve this kind of problem, also is to use an array, the elements of the highest priority, each time the same team can keep the operation stability of the team and the team in O (logn), although the average queue team is O (1), but from the perspective of a team the team average complexity, performance gap is O (log) and O (n squared). Let’s take a look at the performance difference between the heap and the normal queue when processing the outbound/enqueue of 100,000 pieces of data.

The heap can still process data in less than a second, and the performance gap between them only gets bigger as the data size increases.

What is a heap?

[37, 22, 26, 12, 11, 25, 7, 3, 8, 10], this looks like an array at first glance, but if we arrange it in a binary tree structure, the following structure will appear:

And this is a heap, which has several characteristics:

1. The priority of the parent node is higher than or equal to that of the child node

The most notable feature of the heap is that all the parent nodes have a priority higher than or equal to that of the child nodes. Here the heap is the largest, the root node has the largest value, and this is true for any order of nodes. There is also the minimum heap, where all the parent nodes have values less than or equal to the child, and the root node has the smallest value.

2. Complete binary tree

The heap is arranged as a complete binary tree, except for the lowest leaf node, which is a full binary tree, and all leaves are placed to the left of the tree. As explained in the binary tree properties section, using an array is the best way to store a full binary tree.

3. The dynamic

Similar to binary search trees, the heap has its own set of operations when adding or removing elements to the built heap, so as not to break the properties of the heap, no matter how many elements are added or removed at any time.

Implement maximum heap from zero

The biggest problem with using an array to represent a binary tree is that the current node does not have a pointer to the child node. In fact, this problem can be solved easily. The parent node and the left and right child nodes can be determined by the index of the current node, which is also the advantage of using array storage:

With this difficulty solved, we first write the largest number of auxiliary functions:

Class MaxHeap {constructor () {enclosing _data while forming = [] / / store data in a pile of} getParent (I) {/ / get the parent node return (I - 1) / 2 | 0 / / down integer} GetLeftChild (I) {return I * 2 + 1} getRightChild(I) {return I * 2 + 2}} getRightChild(I) {return I * 2 + 2}}Copy the code

Increasing (siftUp)

To add any element to the heap without breaking the nature of the heap, first push the element to the end of the heap array. Then the element needs to be compared to its parent, and if it is larger than its parent, it needs to swap places between them. After switching positions, the comparison continues with the parent node of the previous current position. If it is still larger than the parent node, the switch continues until it is no larger than the parent node or reaches the root node. This operation, also called siftUp, floats the node step by step.

Class MaxHeap {constructor() {this._data = [] // Store data in the heap}... Push (val) {this._data.push(val) {this._data.push(val) {this._data.push(val) {this._data. Push (val) {this._data. Push (val) {this._data If (this._data[I] > this._data[parent]) {this.swap(I, Parent) // swap position this.siftup (parent) // float up}} swap(I, j) {// Swap position of two elements of array [this._data[I], this._data[j]] = [this._data[j], this._data[i]] } }Copy the code

Take (siftDown)

All this work is done to get the highest priority out of the queue. Obviously, you can just get out of the queue from the top of the heap, but when you get out of the queue, the root node is empty, which breaks the nature of the heap. The last element of the heap array is placed at the top of the heap. Then the top element is compared with its left and right children, and the largest child is swapped until it is larger than two children or reaches the root node.

Class MaxHeap {constructor() {this._data = [] // Store data in the heap}... Sift () {if (this._data.length === 0) {return} const Max = this._data[0] this.swap(0, This._data.length - 1) // Swap this._data.pop() // remove the end of the queue this.siftDown(0) // sink the node to return Max // return the element that should exit the queue} SiftDown () {const {_data} = this let Max = this.getLeftChild(I) if (Max >= _data.length) { Return} if (Max + 1 < _data.length && _data[Max + 1] > _data[Max]) {// If there is a right child and the right child is bigger than the left child, Max ++} if (_data[I] < _data[Max]) {// If the child is larger than the current node, This.swap (I, Max) // Swap the current node with the child this.siftdown (Max) // continue recursion at the child's location}}}Copy the code

The key to the sinking operation is to find the older of the two child nodes to swap, and then recurse at the location of the child node. The above are the two most important operations in the heap, joining and leaving the heap, has been completed from zero, but there are two heap auxiliary functions, can be more convenient and fast to complete the corresponding operations of the heap.

Replace (replace)

We need to add a value to the heap at the same time as the queue. We can use the two methods previously implemented. First sift out the top element of the heap, and then push in an element, but this will perform O(logn) twice.

Class MaxHeap {constructor() {this._data = [] // Store data in the heap}... Replace (val) {if (this._data.length === 0) {return} const Max = this._data[0] // Cache the queue element this._data[0] = val // This.siftdown (0) // the top of the heap to perform a sink return Max // queue}}Copy the code

Array fast heapify

How do I quickly convert an array to a heap? It is possible to simply add each item of the array to the heap, but it is not the fastest process. Here, we can make use of the characteristics of a complete binary tree to start from the parent node of the last leaf node and sink all nodes between the starting node and the root node. That way, on average, I can cut out half of the nodes, and I can go from O(nlogn) to O(n) by proof THAT I don’t understand.

Class MaxHeap {constructor(arr = []) {// The constructor supports passing in arrays, If (array.isarray (arr) && arr.length > 0) {this._data = [...arr] this.heapify(this._data)} else {this._data = [] // Store data in heap}}... heapify(arr) { let parent = this.getParent(arr.length - 1) while (parent >= 0) { this.siftDown(parent) parent-- } } }Copy the code

The application of the heap

In the above code we have implemented a heap from zero, but what does it do? Here are a few examples to illustrate the power of this data structure and its subtlety in dealing with specific problems.

Heap sort left

Since the top of each heap is the maximum value, we can queue the whole heap in order, which implements a descending sort. According to this property, build a minimum heap to implement a sorting algorithm try!

function heapSort(arr) { let last = ((arr.length - 2) / 2) | 0; // Just start from the parent of the last leaf const ret = []; while (last >= 0) { siftDown(arr, last, arr.length); // Sink half of the node to heap last--; } while (arr.length > 0) { ret.push(arr[0]); [arr[0], arr[arr.length-1]] = [arr[arr.length-1], arr[0]]; // Swap the first and last elements arr.pop(); SiftDown (arr, 0, arr.length); } return ret; Function siftDown(arr, I, n) {let left = I * 2 + 1; if (left >= n) { return; } if (left +1 < n &&arr [left] > arr[left +1]) { } the if (arr [left] < arr [I]) {/ / let elements sinking [arr [left], arr [I]] = [arr [I], arr [left]]. siftDown(arr, left, n); }}}Copy the code

Although we have done the sorting task, this algorithm creates O(n) space to store the new sorted array. Is it possible to save this extra space? Yes, we can use the heap sorting method, we implement it!

In-situ heap sort ↓

That is, sort on top of the original array without any extra space. It works by using the largest heap, swapping the top element with the bottom element, shrinking the right edge, rebuilding the heap, and so on.

function heapSort(arr) { let last = ((arr.length - 1) / 2) | 0; while (last >= 0) { siftDown(arr, last, arr.length); // use the maximum heap last--; } let r = arr.length; while (r > 0) { [arr[0], arr[r - 1]] = [arr[r - 1], arr[0]]; // Swap the top of the heap with the last element r--; SiftDown (arr, 0, r); } function siftDown (arr, I, n) {let left = I * 2 + 1; if (left >= n) { return; } if (left + 1 < n &&arr [left] < arr[left + 1]) { } the if (arr [I] < arr [left]) {/ / sink small element [arr [I], arr [left]] = [arr [left], arr [I]]. siftDown(arr, left, n); }}; }Copy the code

1046- Weight of the last stone ↓

There is a pile of stones, and each stone has a positive integer weight. In each round, pick two of the heaviest stones and smash them together. Suppose the stones weigh x and y, and x <= y. The possible results of crushing are as follows: if x === y, then both stones will be completely crushed; If x! == y, then the stone weighing x will be completely crushed, and the stone weighing Y will have a new weight of Y-x. In the end, there will be no more than one stone left. Returns the weight of this stone. If there are no stones left, 0 is returned. Input: [2,7,4,1,8,1] First 7 and 8 get 1, so the array is converted to [2,4,1,1,1], then 2 and 4 get 2, so the array is converted to [2,1,1,1], then 2 and 1 get 1, so the array is converted to [1,1,1], then 1 and 1 get 0, The final array is converted to [1], which is the weight of the remaining rock.Copy the code

This taking place every time is to find the two largest stone, that we use the maximum heap to solve this problem is very suitable for, can take two elements on the top of the heap element, and then put the absolute value of subtraction in the pile tip, and sinking again to maintain the nature of the heap at a time, when the elements in the heap when only one end of the process. The code is as follows:

const lastStoneWeight = function (stones) { let last = ((stones.length - 2) / 2) | 0; While (last >= 0) {// Heap siftDown(stones, last); last--; } while (stones. Length > 1) {// When only one element ends the loop swap(stones, 0, Pop () const first = stone.pop () const first = stone.pop (); Const second = stones[0]; Const diff = math. abs(first-second) const diff = math. abs(first-second) } return stones[0]; function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] } function siftDown(arr, i) { let left = i * 2 + 1; if (left >= arr.length) { return; } if (left + 1 < arr.length && arr[left] < arr[left + 1]) { left++; } if (arr[left] > arr[i]) { swap(arr, left, i) siftDown(arr, left); }}};Copy the code

The heap is implemented using arrays, so it is important to consider that arrays are not displaced as much as possible.

215- The KTH largest element in the array ↓

Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element. Example: input: [3,2,1,5,6,4] and k = 2 output: 5Copy the code

The easiest way to do this is to use sort and then select the element with the corresponding subscript, but if the interviewer asks this question, it will not be such a violent O(nlogn) solution. With the help of the heap learned in this chapter, we can hand in O(nlogk) solution. This optimization is useful if you’re looking for the 100th digit of a million data points.

First illustrate ideas, build a minimum heap, k element after meet if is greater than the pile top, and replace the top of the heap element, implement the sinking operation, maintain the nature of the heap, finally finished when the whole array traversal, the minimum heap heap top element is the need to return, because is bigger than the first k all below at the top of the heap.

Largest = function (nums, k) {const minHeap = [] for (let I = 0; i < nums.length; I ++) {if (I < k) {// The heap size is not yet k minheap.push (nums[I]) // siftUp(minHeap, Else if (nums[I] > minHeap[0]) {minHeap[0] = nums[I] // Replace the heaptop element if the next element is larger than the heap SiftDown (minHeap, 0)} return minHeap[0]; Function siftUp (nums, I) {const parent = (I - 1) / 2 | 0 if (nums [I] < nums [parent]) {/ / will be a small buoyancy swap (nums, I, parent) siftUp(nums, parent) } } function siftDown(nums, i) { let l = i * 2 + 1 if (l + 1 > nums.length) { return } if (l + 1 <= nums.length && nums[l] > nums[l + 1]) { l++ // If (nums[I] > nums[l]) {// swap(nums, I, l) siftDown(nums, l)}} function swap(nums, I, l) parent) { [nums[i], nums[parent]] = [nums[parent], nums[i]] }Copy the code

373- Find and the smallest k-pair number ↓

Given two ascending integer arrays nums1 and nums2, and an integer k. Define a pair of values (u,v) where the first element comes from nums1 and the second from nums2. Find the sum of the smallest k-pair numbers (U1,v1), (u2,v2)... Vitamin k (UK). Input: nums1 =,7,11 [1], nums2 = minus [2], k = 3 output: [1, 2], [1, 4], [1, 6] explanation: Return sequence of the first 3 logarithmic: [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11], [7], [11, 4], [11]Copy the code

Iterating through two nested arrays in turn is inevitable, but what we can optimize for this problem is the storage of the result, sorting after each calculation without violence. Use the heap, maintain a maximum heap of k size, each time the calculated value is compared to the top of the heap, if smaller than the top of the heap, put into the heap, and finally reorder the k size of the heap.

var kSmallestPairs = function (nums1, nums2, k) { const heap = [] for (let i = 0; i < nums1.length; i++) { for (let j = 0; j < nums2.length; J++) {if (heap. Length = = = k && nums1 nums2 [I] + [j] > = (heap [0] [0] + heap [0] [1])) {/ / because are ascending array, so when the and is greater than the pile top, // Then the next loop must also be greater than, so break out of the loop. Break} if (heap.length < k) {// Heap. push([nums1[I], nums2[j]]) siftUp(heap, Else if ((nums1[I] + nums2[j]) <= sum(heap[0])) {heap[0] = [nums1[I], heap[0] = heap[I], heap[0] = heap[I], heap[0] = heap[I], heap[0] = heap[I] Nums2 [j]] // siftDown(heap, 0) // Maintain maximum heap}}} return heap.sort((a, B) = > (a [0] + [1] a) - (b + b [1] [0])) / / for it is the maximum heap, all return to the ascending order of}; function siftUp(heap, i) { const parent = (i - 1) / 2 | 0 if (sum(heap[i]) > sum(heap[parent])) { swap(heap, i, parent) siftUp(heap, parent) } } function siftDown(heap, i) { let left = i * 2 + 1 if (left >= heap.length) { return } if (left + 1 < heap.length && sum(heap[left]) < sum(heap[left + 1])) { left++ } if (sum(heap[i]) <= sum(heap[left])) { swap(heap, i, left) siftDown(heap, Left)} function sum(arr) {return arr[0] + arr[1]} function swap(arr, I, j) {[arr[I], arr[j]] = [arr[j], arr[i]] }Copy the code

The last

Writing so much, it is not difficult to find nothing more than the writing of siftup and siftdown functions, as long as you master these two operations of the heap, basically speaking, the heap has mastered 90%. The most important thing is to be familiar with the idea of heap. It is very suitable to use heap for similar topics before K, and the dynamic nature of heap is very suitable for processing data when new elements are added at any time. There is such a cool data structure

This chapter github source code

Data structure and Algorithm of front-end Science (8) : Implementation and application of Trie tree, the artifact of word prefix matching