preface
As for the origin of my relationship with Heap, it can be dated back to two years ago. At that time, I was young and energetic. As soon as I entered the front door, I expected to open the door of Dachang in one year and reach the peak of my life in three years.
It was he, the man, who pulled me out of the clouds with a sleaze and a decent algorithm called 215. The KTH largest element in the array
And this is where I started formally learning algorithms, and there’s always been this nonsense that when you think you should learn an algorithm, that’s the best time to learn an algorithm; As a young man, I even believed his nonsense and thought it was not the right time, until I was struck by the man above and vowed to become a topk vegetable chicken
However, after two years, turning around, I finally met the enemy of my life for the second time, and I lack of wandering, confused, do not know how to start, finally reluctantly sort, was the interviewer doubt?? Why are you still in order, feeling confused, so, I picked up a pile of such a topic, swear to three things.
The body of the
You think I’m going to start talking about algorithms? How is it possible, I am a vegetable chicken, how can not compare with the big guy on the market to speak clearly, speak thoroughly, I am simply looking for an excuse, will own this week to write some topics and analysis posted up, for the use of JS partners brush;
So the analysis of vegetable chicken is certainly not as good as that of the big guys, but the pit’s… Stone is also useful, so what is my use, that is, my thinking may be similar to many of me, so you think of the wrong place, I must also think of the wrong place, for example, after creating a binary heap, why the array is not already sorted, am I wrong? No, XDM, this is a mistake many newbies make, thinking that when you create a heap, you end up with a perfect array, with only one layer of real rice on the surface and sand on the inside;
So, the advantage of novice thinking is that they may not bother to explain what is obviously available, and novices, like me, may need to write notes or something, so it helps a little… .
The above view is also my rookie thinking, or higher thinking, I this is childish, do not accord with the actual, but that how, I just wrote, I cool on the line ah.
So here’s the body;
The text plus
A heap is a data structure that dynamically evaluates to an extreme value, so when you need to constantly evaluate an extreme value, you can consider using a heap
Warm tips, it is suggested that each question should be a new heap, so as to discover the beauty of the heap, in fact, it will not have to use bubbles to do topK again.
This is the end of the article, if there are 10 concerns, then update the next part, DP or tree, THX.
By the way, the guy’s web page, won’t you check it out?
Creation of binary heap
Analysis — small top reactor
- Here is a small top heap, characterized by the fact that the value of the root node is smaller than the value of the child nodes, usually used as the classic pre-k large
- There are two main methods,
- One is the rise, which is mostly used to clean up the heap when you’re building it
- This. Data [0] is used because this method is usually used after the whole heap is built
- Other methods are not impossible, just to ensure flexibility, temporarily do a simple version, later consider, because the more methods, in fact, the worse the compatibility
class MinHeap {
constructor(len) {
this.data = [];
this.data[0] = len; // The first node is used to store the size of the heap -- useful for certain environments
}
/ / down
down(index) {
const size = this.data[0];
while (index << 1 <= size) {
let child = index << 1;
if(child ! == size &&this.data[child] > this.data[child + 1]) {
child += 1; // If the right node is smaller, the right node is used as the next node to connect to disks
}
if (this.data[index] > this.data[child]) {
// Switch
[this.data[index], this.data[child]] = [
this.data[child],
this.data[index],
];
index = child;
} else {
// As long as one of them fails, there is no need to search further
break; }}}// Start at the bottom
upper() {
This.data [0] is not used here because the heap currently built may not have reached its maximum size
let index = this.data.length - 1;
while (index >> 1 > 0) {
let father = index >> 1;
if (this.data[index] < this.data[father]) {
// If the child node is smaller than the parent node, go online
[this.data[index], this.data[father]] = [
this.data[father],
this.data[index],
];
index = father;
} else {
break; }}}}Copy the codeAnalysis — Big top reactor
- Compared to the original small top heap, this version of the big top heap adds two methods, POP and Add
- The add method can be written where the heap is used, but to make it match the first value of the heap, it is written inside the class method to facilitate the addition of size
- Pop is to pull out the top of the heap,
The heap is designed to solve dynamic maximaAnd the existence of the data structure, so it is necessary to take out the collation process.
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0; // The first value is the current heap size
}
down(index) {
const len = this.data.length; // is the subscript limit
while (index << 1 < len) {
let child = index << 1;
if(child ! == len &&this.data[child + 1] > this.data[child]) {
child++;
}
if (this.data[child] > this.data[index]) {
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break; }}}upper() {
let index = this.data[0]; // Maximum subscript
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[index] > this.data[father]) {
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break; }}}add(value) {
// Add it to the end first
this.data.push(value);
this.data[0] + +;// size also add
this.upper(); // Let's get it sorted
}
// Pop up the top of the heap element
pop() {
const last = this.data[0];
[this.data[1].this.data[last]] = [this.data[last], this.data[1]].// Swap the top and bottom of the heap
const ret = this.data.pop();
this.data[0]--;
this.down(1); / / finishing
returnret; }}Copy the code215. The KTH largest element in an array
Analysis of the
- This is a classic fried chicken problem, can use bubbling, quick row, one of the most classic method, is the small top pile evaluation — as the basic topic of the textbook
- So if we want the KTH largest, we’re going to maintain a small top heap of K size, and then the top of the heap is the KTH largest
- We then iterate over the nums, initializing a small top heap of K size, and comparing the remaining values with the top of the heap;
- Anything that’s bigger than the top of the heap, you just replace the top of the heap, but then the top of the heap isn’t necessarily the minimum in the small top heap, so you need to go down and clean up the small top heap
- And when you’re done walking through it, you have a little top heap, and then you go straight to the top of the heap and the top element is the KTH largest;
- Time complexity: {O(N*L) — where N is the size of the array and L is the height of the binary heap, L is relatively small, so the complexity can be said to be close to linear
- Space complexity: O(M){O(M)}O(M) — where M is the K value, because a K heap is to be maintained
// 215. The KTH largest element in the array
// MinHeap is the class above
var findKthLargest = function (nums, k) {
// Create a small top heap of size K
const minHeap = new MinHeap(k);
const len = nums.length;
for (let i = 0; i < len; i++) {
if (i < k) {
// Initialize the heap
minHeap.data.push(nums[i]);
minHeap.upper();
} else {
// This time to consider whether to press into the small top heap
// If the following value is greater than the top value of the small top heap, we can know whether to replace it or not
if (nums[i] > minHeap.data[1]) {
minHeap.data[1] = nums[i];
minHeap.down(1); }}}return minHeap.data[1]};Copy the code1046. The weight of the last stone
Analysis — Big top reactor
- According to the problem, we need to take the maximum and submaximum value of an array. After some operation, we return the calculated value to the array. Then we loop until the array length is at most 1
- So it’s dynamic maxima, and you can think about using the heap
- Define a pop method to get the top of the heap each time and tidy up the big top of the heap. Define add to add elements to the heap
- This returns either 1 or 0 each time two elements are fetched, until the heap element is less than 2, which returns either the element in the heap or 0
- Space complexity is maintenance heap, so O(N){O(N)}O(N), time complexity O(NlogN){O(NlogN)}O(NlogN)
// the weight of the last stone
var lastStoneWeight = function (stones) {
// Maintain a large top heap
const heap = new MaxHeap();
for (let i = 0; i < stones.length; i++) {
heap.add(stones[i]);
}
while (heap.data[0] > 1) {
// 1. Fetch two Max values at a time
const first = heap.pop();
const second = heap.pop();
// 2. Subtract and put back
const temp = first - second;
if(temp) { heap.add(temp); }}return heap.data[0]? heap.data[1] :0
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0; // The first value is the current heap size
}
down(index) {
const len = this.data.length; // is the subscript limit
while (index << 1 < len) {
let child = index << 1;
if(child ! == len &&this.data[child + 1] > this.data[child]) {
child++;
}
if (this.data[child] > this.data[index]) {
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break; }}}upper() {
let index = this.data[0]; // Maximum subscript
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[index] > this.data[father]) {
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break; }}}add(value) {
// Add it to the end first
this.data.push(value);
this.data[0] + +;// size also add
this.upper(); // Let's get it sorted
}
// Pop up the top of the heap element
pop() {
const last = this.data[0];
[this.data[1].this.data[last]] = [
this.data[last],
this.data[1]]// Swap the top and bottom of the heap
const ret = this.data.pop();
this.data[0]--;
this.down(1); / / finishing
return ret
}
}
Copy the codeMerge K ascending linked lists
Heap analysis —
- The main idea here is to treat the list as an element of the heap, with the value of the list head as the base for creating the small top heap
- I’m going to have K ascending lists merged, so I’m going to take the minimum of K, and I’m going to put it into my own list, and I’m going to have a merged ascending list
- Space complexity is the maintenance heap, so O(N∗M){O(N*M)}O(N∗M), where N is the length of lists and M is the average length of linked lists
- Time complexity: Extract values and merge them into a new linked list — O(N∗M){O(N*M)}O(N∗M)
Merge K ascending linked lists
/** * @parse * 1. Create a small top heap */ with the list header as the judge element
var mergeKLists = function(lists) {
let emptyNode = new ListNode() // Create your own
// Build a heap
const minHeap = new MinHeap()
for (let i = 0; i < lists.length; i++) {
const head = lists[i];
if(head){
minHeap.add(head)
}
}
let cur = emptyNode;
while(minHeap.data[0]){
cur.next =new ListNode(minHeap.pop())
cur = cur.next
}
return emptyNode.next
};
class MinHeap {
constructor(){
this.data = []
this.data[0] = 0
}
down(index){
const lastIndex = this.data[0]
while(index<<1 <= lastIndex){
let child = index<<1
if(child! == lastIndex &&this.data[child+1].val<this.data[child].val){
child++
}
if(this.data[child].val<this.data[index].val){
[this.data[child],this.data[index]] = [this.data[index],this.data[child]]
index = child
}else{
break}}}upper(){
let index = this.data[0]
while(index>>1 > 0) {let father = index>>1
// Use the header value as the judge
if(this.data[father].val>this.data[index].val){
// Swap the entire list
[this.data[father],this.data[index]] = [this.data[index],this.data[father]]
index = father
}else{
break}}}add(head){
// Add a sorted list,
this.data.push(head);
this.data[0] + +this.upper()
}
// Remove the header value from the heap top list and rearrange it
pop(){
const ret = this.data[1].val
this.data[1] = this.data[1].next
if(!this.data[1]) {// The list is undefined
[this.data[1].this.data[this.data[0]]] = [this.data[this.data[0]],this.data[1]]
this.data.pop()
this.data[0] -}this.down(1) / / finishing
return ret // Returns a value}}Copy the codeAnalyze — divide and conquer
- Multiple sorted lists are hard to handle, but what about merging two sorted lists?
- Combine two ordered lists, put them in the list and continue, and then combine one
- Use divide and conquer, if more than 2 lists, split the processing, mergeKLists(ARR) finally get a sorted list, so each time can be divided, and then finally merge governance;
- The time complexity of merging two lists is O(N){O(N)}O(N), and the complexity of dividing and dividing M lists is O(logM){O(logM)}O(logM), so O(NlogM){O(NlogM)}O(NlogM), where N is the length of the list, M is the number of linked lists
/** * @parse * 1. Multiple sorted lists are difficult to handle, so how about merging two sorted lists? * 2. Combine two ordered lists, then add them to list, then add one to list * 3. Use divide and conquer, if more than 2 lists, split the processing, mergeKLists(ARR) finally get a sorted list, so each time can be divided, and then finally merge governance; ${O(logM)}${O(logM)}${O(logM)}${O(logM)}$
var mergeKLists = function(lists) {
const len =lists.length
// return lists. Reduce ((prev,cur) => mergeTwoList(prev,cur)
// Divide-and-conquer reduces N to logN
if(len<1) return null
if(len === 1) return lists[0]
if(len === 2) return mergeTwoList(lists[0],lists[1])
const mid = len>>1
return mergeTwoList(mergeKLists(lists.slice(0,mid)),mergeKLists(lists.slice(mid)))
};
// Merge two ordered lists
function mergeTwoList (list1,list2){
const emptyNode = new ListNode()
let cur =emptyNode
while(list1 && list2){
if(list1.val<list2.val){
cur.next= list1
list1 = list1.next
}else{
cur.next= list2
list2 = list2.next
}
cur = cur.next
cur.next = null
}
if(list1) cur.next = list1
if(list2) cur.next = list2
return emptyNode.next
}
Copy the code451. Sort by frequency of character occurrence
Analysis of the
- Since the new assembly is based on the appearance rating, the string is iterated first, and the characters and occurrence frequency are stored as a group of items using map — the time and space complexity is O(N){O(N)}O(N).
- At this time in fact, as long as according to the frequency from to small arrangement, and then one by one out of the reload can be
- Here we use heap sort, but item is no longer a simple number, but an array [key,value], so we can tweak the method accordingly
- The heap row is the time complexity: O(NlogN){O(NlogN)}O(NlogN), the final space complexity is O(N){O(N)}O(N).
// sort by character frequency
var frequencySort = function (s) {
let ret = "";
if(! s)return s;
const map = new Map(a);const heap = new MaxHeap();
for (let i = 0; i < s.length; i++) {
const item = s[i];
if (map.has(item)) {
map.set(item, map.get(item) + 1);
} else {
map.set(item, 1); }}// Add the element to the heap with the value [key,value]
for (let item of map.entries()) {
heap.add(item);
}
while (heap.data[0]) {
const item = heap.pop();
ret += item[0].repeat(item[1]);
}
return ret;
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0;
}
down(index) {
const lastIndex = this.data[0]; // Subscript of the last value
while (index << 1 <= lastIndex) {
let child = index << 1;
if( child ! == lastIndex &&this.data[child + 1] [1] > this.data[child][1]
) {
child++;
}
if (this.data[child][1] > this.data[index][1]) {
// Note that item is an array, so the second value is used for comparison, but the entire item is swapped
[this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break; }}}upper() {
let index = this.data[0];
while (index >> 1 > 0) {
const father = index >> 1;
if (this.data[father][1] < this.data[index][1]) {
// Note that item is an array, so the second value is used for comparison, but the entire item is swapped
[this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break; }}}add(item) {
this.data.push(item);
this.data[0] + +;this.upper();
}
pop(){[this.data[1].this.data[this.data[0]]] = [
this.data[this.data[0]],
this.data[1]];this.data[0]--;
const temp = this.data.pop();
this.down(1)
return temp
}
}
Copy the code378. The KTH smallest element of an ordered matrix
Analysis of the
- So this is bottomK with an array of items, and normal top K with an array of elements
- When using heap, you just need to compare the down and upper functions
- However, one difference is that K may be larger than Len(matrix) of the two-dimensional array, so instead of directly creating a k-big top heap to take the top of the heap, you need to group all the elements of the two-dimensional array into a small top heap of Len size, and then fetch K times
- This shows that there are two ways to solve the problem of top K: either set the heap of K large/small, and constantly replace with elements, or set the heap of all elements, and pop K values;
- Time/space complexity O(NlogN){O(NlogN)}O(NlogN)
The KTH smallest element in the ordered matrix
/** * @analysis -- KTH small * 1. This is a sorted matrix, so we can use the small top heap to transfer the matrix elements to the small top heap, each time from the top to the KTH */
var kthSmallest = function(matrix, k) {
const minHeap = new MinHeap()
for(let i = 0; i<matrix.length; i++){ minHeap.add(matrix[i]) }const ret = []
while(--k){
minHeap.pop()
}
return minHeap.pop()
};
class MinHeap {
constructor(){
this.data = []
this.data[0] = 0
}
down(index){
const lastIndex = this.data[0]
while(index<<1 <= lastIndex){
let child = index << 1
if(child! ==lastIndex &&this.data[child+1] [0] <this.data[child][0]){
child++
}
if(this.data[child][0] <this.data[index][0{[])this.data[child], this.data[index]] = [this.data[index], this.data[child]]
index = child
}else {
break}}}upper() {
let index = this.data[0]
while(index >>1 > 0) {let father = index >> 1
if(this.data[father][0] >this.data[index][0{[])this.data[father], this.data[index]] = [this.data[index], this.data[father]]
index = father
}else {
break}}}add(item){
this.data.push(item)
this.data[0] + +this.upper()
}
// Instead of popping the item directly, just pop the first letter on the top of the heap, and then sort it out
pop(){
const temp = this.data[1].shift()
if(!this.data[1].length){
// The array is empty
this.data[1] = this.data[this.data[0]]
this.data.pop()
this.data[0] -}this.down(1)
return temp
}
}
const ret = kthSmallest([[1.5.9], [10.11.13], [12.13.15]],8)
console.log(ret)
Copy the code1054. Equidistant bar codes
Analysis of the
- In order to ensure that the two are not equal, it must ensure that the number of the bar code must be finished first, to prevent the other row will save it itself;
- Therefore, map is used to store all barcode values (keys) and quantities (values).
- At this point, it is similar to the weight of the last stone of 1046;
- But there’s another difference, which is that every time you take the largest two pieces, you can only take one piece and arrange it, and then you have to put the rest back, making sure that each time you take the largest two pieces; For example, in this problem, we are grinding stone, each time one layer of skin, each time with the last stone to grind, and 1046. The weight of the last stone is just two hits;
- When map is stored, the time complexity and space complexity are both O(N){O(N)}O(N), where N is the length. Heap row, I don’t know what this is, but it’s also order NlogN {O(NlogN)} order NlogN
// 1054. Equidistant bar codes
var rearrangeBarcodes = function (barcodes) {
// 1. Store the bar code values and quantities in map
const map = new Map(a);for (let i = 0; i < barcodes.length; i++) {
const item = barcodes[i];
if (map.has(item)) {
map.set(item, map.get(item) + 1);
} else {
map.set(item, 1); }}// 2. Create a maximum heap
const heap = new MaxHeap();
for (let item of map.entries()) {
heap.add(item); // [key,value]
}
// 3. Take out the largest two items each time and rewrite the arrangement
const ret = [];
while (heap.data[0] > 1) {
// The default is to ensure that there is an answer, so even if there is an item at the end, the corresponding value is only 1
// However, if the condition is not known, then the value can be used to determine whether success is achieved
const first = heap.pop();
const second = heap.pop();
/ / Error: Error
// while(second[1]--){
// ret.push(first[0])
// ret.push(second[0])
// first[1]--
// }
ret.push(first[0]);
first[1]--;
ret.push(second[0]);
second[1]--;
// Then you have to put it back
if (first[1]) {
// If there is any value, put it back in the heap
heap.add(first);
}
if (second[1]) {
// If there is any value, put it back in the heapheap.add(second); }}if (heap.data[0]) {
ret.push(heap.pop()[0]);
}
return ret;
};
class MaxHeap {
constructor() {
this.data = [];
this.data[0] = 0;
}
down(index) {
const lastIndex = this.data[0];
while (index << 1 <= lastIndex) {
let child = index << 1;
if( child ! == lastIndex &&this.data[child + 1] [1] > this.data[child][1]
) {
child++;
}
if (this.data[child][1] > this.data[index][1{[])this.data[child], this.data[index]] = [
this.data[index],
this.data[child],
];
index = child;
} else {
break; }}}upper() {
let index = this.data[0];
while (index >> 1 > 0) {
let father = index >> 1;
if (this.data[father][1] < this.data[index][1{[])this.data[father], this.data[index]] = [
this.data[index],
this.data[father],
];
index = father;
} else {
break; }}}add(item) {
this.data.push(item);
this.data[0] + +;this.upper();
}
pop(){[this.data[1].this.data[this.data[0]]] = [
this.data[this.data[0]],
this.data[1]];const item = this.data.pop();
this.data[0]--;
this.down(1);
returnitem; }}console.log(rearrangeBarcodes([7.7.7.8.5.7.5.5.5.8]));
Copy the code