The introduction
Heap is the essential knowledge of front-end advancement, and also the key and difficult points of the interview, such as memory heap and garbage collection, Top K problem, etc., this article will sort out the whole heap system from the basics, according to the following steps:
What is a pile of
How to build the heap
Heap sort
Memory heap and garbage collection
Top K problem
Median problem
Finally, let’s do a leetcode problem to deepen our understanding
Let’s get started :point_down:
A heap,
A heap is one that meets the following two conditions:
The heap is a complete binary tree
Any node on the heap must be greater than or equal to (large top heap) or less than or equal to (small top heap) its left and right child values
If any node on the heap is greater than or equal to the child node value, it is called the big top heap
If any node on the heap is less than or equal to the child node value, it is called the small top heap
That is, in the big top heap, the root node is the largest element in the heap;
In the small top heap, the root node is the smallest element in the heap;
The heap can be represented as an array. Given the subscript I of A node, the parent node must be A[I /2], the left child is A[2i], and the right child is A[2i+1].
How to create a large (small) top heap
As we explained in the previous section, a complete binary tree is suitable for array storage, and a heap is a complete binary tree, so it can be stored directly using array storage:
Function Heap() {let items = [,]} function Heap() {let items = [,]}
There are two common ways:
Insertion creation: Implement a large (or small) top heap, one node at a time
In situ creation: Also called heapification, the implementation of a large top heap (or small top heap) given a group of nodes
Three, plug – in build heap
Insert node:
Insert the node to the end of the queue
Bottom-up heaping-compare the inserted node to its parent. If the inserted node is larger than the parent (big top heap) or smaller than the parent (small top heap), the inserted node and the parent are adjusted
Repeat the previous step until swapping is not required or to the root node, at which point the insertion is complete.
Code implementation:
Function insert(key) {items.push(key) let I = items.length-1 while (I /2 > 0 && items[I] > items[I /2]) { swap(items, i, i/2); // switch I = I /2; } function swap(items, I, j) {let temp = items[I] items[I] = items[j] items[j] = temp} Time complexity: O(logn), is the height of the tree
Four, in situ pile (heap)
Suppose a set of sequences:
Let arr = [,1, 9, 2, 8, 3, 7, 4, 6, 5] There are two ways to build heap in situ: one is to inherit the idea inserted above, that is, to build heap from front to back, bottom-up; The opposite is to build a heap from back to front and from top to bottom. Among them
Bottom-up heapification: A node is compared to its parent, and if the node is larger than the parent (big top heap) or smaller than the parent (small top heap), the node and the parent are adjusted
Top-down heapification: a node is compared with its left and right children, and if there are left and right children larger than this node (big top heap) or smaller than this node (small top heap), then the maximum (big top heap) or minimum (small top heap) of the child node is swapped with it
So, bottom-up heaps are adjusting nodes and their parents (going up), while top-down heaps are adjusting nodes and their left and right children (going down).
- From front to back, bottom-up stacking
Let’s take the small top heap as an example,
Code implementation:
Var heapSize = 1 function buildHeap(items) {while(heapSize < items. heapSize ++ heapify(items, heapSize) } }
Function heapify(items, I) {// While (math.floor (I /2) > 0 && items[I] < items[math.floor (I /2)]) {swap(items, i, Math.floor(i/2)); // switch I = math.floor (I /2); }}
function swap(items, i, j) { let temp = items[i] items[i] = items[j] items[j] = temp }
Var items = [,5, 2, 3, 4, 1] buildHeap(items) console.log(items) // [empty, 1, 2, 3, 5, 4] Test successful
- Build heap from back to front, top-down
Here’s an example of a small top heap
Note: Backward-forward does not start with the last element in the sequence, but with the last non-leaf node, because leaf nodes have no children and do not require top-down heaping-up.
The parent of the last child node is N /2, so the heap starts from the node at position N /2:
Code implementation
// items: original sequence // heapSize: Function buildHeap(items, heapSize) {for (let I = math.floor (heapSize/2); function buildHeap(items, heapSize) { i >= 1; –i) { heapify(items, heapSize, i); }} function heapify(items, heapSize, I) {while (true) {var maxIndex = I; if(2i <= heapSize && items[i] > items[i2] ) { maxIndex = i2; } if(2i+1 <= heapSize && items[maxIndex] > items[i2+1] ) { maxIndex = i2+1; } if (maxIndex === i) break; swap(items, i, maxIndex); // swap I = maxIndex; } } function swap(items, i, j) { let temp = items[i] items[i] = items[j] items[j] = temp }
Var items = [,5, 2, 3, 4, 1] var items = [,5, 2, 3, 4, 1] HeapSize = items.length -1 buildHeap(items, items.length -1) console.log(items) // [empty, 1, 2, 3, 4, 5] The test is successful
Five, sorting algorithm: heap sort
- The principle of
Heap is a complete binary tree, it can use an array of storage, and big top of the heap maximum value is stored in the root node (I = 1), so we can always choose big pile top root node and heaps of exchange, the last node in the maximum effective sequence at this time of the last, minus 1 and effective sequence, effective heap remains fully binary tree structure, and then the heap, To become the new big top heap, repeat this operation until the effective heap length is 0, and the sorting is complete.
The complete steps are as follows:
Convert the original sequence (n) into a large top heap
Set the effective sequence length of the heap to n
Swap the top of the heap element (the first valid sequence) with the last child element (the last valid sequence) and subtract 1 from the valid sequence length
Heap effective sequence, so that the effective sequence is renamed a big top heap
Repeat the above 2 steps until the valid sequence length is 1 and the sorting is complete
-
Dynamic graph demonstration
-
Code implementation
Function heapSort(items) {// Build buildHeap(items, Items.length -1) // Set the initial effective sequence length of the heap to items.length-1 let heapSize = items.length-1 for (var I = items.length-1; i > 1; I –) {// Swap the top element with the last valid child element (items, 1, I); HeapSize –; Heapify (items, heapSize, 1); heapify(items, heapSize, 1); } return items; }
// items: original sequence // heapSize: Function buildHeap(items, heapSize) {for (let I = math.floor (heapSize/2); i >= 1; –i) { heapify(items, heapSize, i); }} function heapify(items, heapSize, I) {while (true) {var maxIndex = I; if(2i <= heapSize && items[i] < items[i2] ) { maxIndex = i2; } if(2i+1 <= heapSize && items[maxIndex] < items[i2+1] ) { maxIndex = i2+1; } if (maxIndex === i) break; swap(items, i, maxIndex); // swap I = maxIndex; } } function swap(items, i, j) { let temp = items[i] items[i] = items[j] items[j] = temp }
Var items = [,1, 9, 2, 8, 3, 7, 4, 6, 5] heapSort(items) // empty, 1, 2, 3, 4, 5, 6, 7, 8, 9
- Complexity analysis
Time complexity: Heap building time is O(n), sorting time is O(nlogn), overall time complexity is O(nlogn)
Space complexity: O(1)
Memory heap and garbage collection
Advanced algorithm 5: Data Structure Stack without fear of the interviewer (leetCode)
Seven, the classic application of heap: Top K question (commonly seen in Tencent, Byte and other interviews)
What is the Top K problem? In simple terms, it is to find the number with the highest frequency of the first K in a set of data, or the number with the highest frequency of the first K (or of course, the first K can be small).
How should we deal with this problem, Nan? Taking the first K value from an array as an example, we can do the following:
Take the first K number from the array and construct a small top heap to traverse the number set starting from the K+1 bit. Each data is compared with the top element of the small top heap. If it is smaller than the top element, no processing is done and the next element is traversed. If it is larger than the top of the heap, the element is replaced with the top of the heap, and then heaped into a small top heap. Once the traversal is complete, the data in the heap is the first K
Traversing the number group requires O(N) time complexity, and once heapification requires O(logK) time complexity, so the time complexity of using heap to solve the problem of Top K is O(NlogK).
Take advantage of the heap to solve the Top K problem
Maybe a lot of people think, well, you can use sort, you don’t have to use heap
In fact, you can use sort to do this, sort the array (can be the simplest quick sorting), go to the first K number is ok, so easy
But what if we need to find Top K in a dynamic array, which can insert or delete elements, do we need to reorder the array every time we need to find Top K? That’s order NlogN each time.
Here we can use the heap, we can maintain a small top heap of K size, and when something is added to the array, compare it to the top element, and if it is larger than the top element, replace that element with the top element, and then heap into a small top heap; If it is smaller than the top of the heap, it is not processed. So the time to solve the Top K problem is only O(logK).
Classical application of heap: median problem
In addition to the Top K problem, a classic application of the heap is the median problem
The median is the number in the middle:
The median of [1, 2, 3, 4, 5] is 3
The median of [1, 2, 3, 4, 5, 6] is 3, 4
That is:
When n % 2! When == 0, the median is: ARr [(n-1)/2]
When n % 2 === 0, the median is: ARr [n/2], ARr [n/2 + 1]
How to use heap to solve the median problem?
There are two heaps to maintain:
Large top heap: used to access the first N /2 small elements, or if n is odd, used to access the first math.floor (n/2) + 1 small top heap: used to access the last n/2 small elements
Then, the median is:
N is odd: the median is the heaptop element of the large top heap
N is even: the median is the heaptop element of the big top heap and the heaptop element of the small top heap
When an array is dynamic, how do you adjust the chatter each time an element is inserted into the array?
If the inserted element is larger than the heap top of the large top heap, the element is inserted into the small top heap; If it is small, it is inserted into the large top heap.
After the entry and exit, if the number of elements in the big top heap and the small top heap does not meet our requirements, we need to constantly move the top elements of the big top heap or the top elements of the small top heap to another heap until the requirements are met
Since heapization is required to insert elements into the heap and move elements on top of the heap, the time complexity of the insert is O(logN), and the median of each insert only needs to return elements on top of the heap, which is O(1).
Median distortion: THE TP 99 problem
TP99 problem: in a time period (such as 5 minutes), count the time consumed by each call of a method (or interface), and sort these time in descending order, and take the 99th value as TP99 value;
For example, an interface is invoked 100 times within 5 minutes, and the time of each invocation ranges from 1ms to 100ms. Arrange the request time from small to large. TP99 is the 100th *0.99 = 99 request time. The better the interface performance is
Therefore, for THE TP99 problem, we can also maintain two heaps, a big top heap and a small top heap. The big top heap holds the first 99% of data, and the small top heap holds the last 1% of data. The data at the top of the heap is the 99% response time we’re looking for.
This section refers to Geek Time: The Beauty of Data Structures and algorithms
Nine,
The heap is a complete binary tree, and the value of any node on the heap must be greater than or equal to (big top heap) or less than or equal to (small top heap) its left and right child node value, push can use array storage method storage, can be built by insertion heap or in situ heap, heap important applications are:
Heap sort
Top K problem: heap, take the first K elements
Median problem: Maintain two heaps, one large (top 50%) and one small (bottom 50%), with odd elements taking the top of the large heap and even elements taking the top of the large and small heap
Storage mechanism is divided into JavaScript code space, stack space and heap space, code space to hold executable code, stack space to hold basic data types and reference types address, heap space used to store a reference type data, when completing an execution context in the call stack, the need for recycling the context and the related data space, Data stored in stack space is collected by ESP pointer, and data stored in heap space is collected by secondary garbage collector (new generation) and main garbage collector (old generation). See front-end Advanced Algorithm 5: Data Structure Stack without fear of the interviewer.
Leetcode: the minimum number of k
Without further ado, let’s have a topic to deepen our understanding:
Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.
Example 1:
Input: arr = [3,2,1], k = 2 output: [1,2] or [2,1] example 2:
Input: arr = [0,1,2,1], k = 1
0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000