This article records some heap knowledge and high-frequency problems. This article summarizes the knowledge and code reference from JavaScript data structures and algorithms.
What is a pile of
- The heap is a special kind
Complete binary tree
. - All the nodes are
Greater than or equal to (maximum heap)
orLess than or equal to (minimum heap)
Its children. - JS is commonly used
An array of
Said the heap. On the left
sideChild nodes
The position is2 * index + 1
.right
sideChild nodes
The position is2 * index + 2
.The parent node
The position of index – 1/2 is rounded.
The application of the heap
- The heap can efficiently and quickly find maximum and minimum values.
- Time complexity: O(1)
Minimum heap implementation
insert
- Insert the value at the bottom of the heap, at the bottom of the array.
- Then move up: swap the value with its parent until the parent is less than or equal to the inserted value.
- Size of the
k
The time complexity of inserting elements into the heap isO(logk)
.
class MinHeap { constructor() { this.heap = []; Heap [i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; // Swap (i1, i2) {[this.heap[i1], this.heap[i1]]; } getParentIndex(I) {return ~~((i-1/2)); } // shiftUp(index) {if (index === 0) return; const pIndex = this.getParentIndex(index); if (this.heap[pIndex] > shit.heap[index]) { this.swap(pIndex, index); this.shiftUp(pIndex); } // Insert (value) {this.heap.push(value); this.shiftUp(this.heap.length - 1); } } const h = new MinHeap(); h.insert(3); h.insert(2); h.insert(1); / / 31 [1]Copy the code
Delete the pile top
- Replace the top of the heap with an element at the end of the array (removing the top directly breaks the heap structure).
- Then move down: swap the new heap top with its children until the children are greater than or equal to the new heap top.
- Size of the
k
The time complexity of removing the heap top from the heap isO(logk)
.
class MinHeap { constructor() { this.heap = []; Heap [i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; // Swap (i1, i2) {[this.heap[i1], this.heap[i1]]; } getParentIndex(I) {return ~~((i-1/2)); } getLeftIndex(I) {return I * 2 + 1; } getRightIndex(I) {return I * 2 + 2; } // shiftUp(index) {if (index === 0) return; const pIndex = this.getParentIndex(index); if (this.heap[pIndex] > this.heap[index]) { this.swap(pIndex, index); this.shiftUp(pIndex); }} // Move the value of this node and its children until the child is greater than or equal to it. const rightIndex = this.getRightIndex(index); if (this.heap[leftIndex] < this.heap[index]) { this.swap(leftIndex, index); this.shiftDown(leftIndex); } if (this.heap[rightIndex] < this.heap[index]) { this.swap(rightIndex, index); this.shiftDown(rightIndex); } // Insert (value) {this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0); } } const h = new MinHeap(); h.insert(3); h.insert(2); h.insert(1); / / [1, 2, 3] h.p op (); / / [2, 3]Copy the code
Gets the top and size of the heap
- Get the top of the heap: Returns the head of the array.
- Get the heap size: Returns the length of the array.
class MinHeap { constructor() { this.heap = []; Heap [i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; // Swap (i1, i2) {[this.heap[i1], this.heap[i1]]; } getParentIndex(I) {return ~~((i-1/2)); } getLeftIndex(I) {return I * 2 + 1; } getRightIndex(I) {return I * 2 + 2; } // shiftUp(index) {if (index === 0) return; const pIndex = this.getParentIndex(index); if (this.heap[pIndex] > shit.heap[index]) { this.swap(pIndex, index); this.shiftUp(pIndex); }} // Move the value of this node and its children until the child is greater than or equal to it. const rightIndex = this.getRightIndex(index); if (this.heap[leftIndex] < this.heap[index]) { this.swap(leftIndex, index); this.shiftDown(leftIndex); } if (this.heap[rightIndex] < this.heap[index]) { this.swap(rightIndex, index); this.shiftDown(rightIndex); } // Insert (value) {this.heap.push(value); this.shiftUp(this.heap.length - 1); } // pop() {this.heap[0] = this.heap. Pop (); this.shiftDown(0); Peek () {return this.heap[0]} size() {return this.heap.length; }}Copy the code
Leetcode topic
215. The KTH largest element in an array
Ideas:
- Build a minimal heap and insert the values of the array in turn into the heap.
- When the heap easily exceeds K, the heap top is removed.
- After insertion, the top of the heap is the KTH largest element.
Code display:
/** * @param {number[]} nums * @param {number} k * @return {number} */ class MinHeap { constructor() { this.heap = []; } swap(i1, i2) { [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; } getParentIndex(i) { return ~~((i - 1) / 2); } getLeftIndex(i) { return i * 2 + 1; } getRightIndex(i) { return i * 2 + 2; } shiftUp(index) { if (index === 0) return; const pIndex = this.getParentIndex(index); if (this.heap[pIndex] > this.heap[index]) { this.swap(pIndex, index); this.shiftUp(pIndex); } } shiftDown(index) { const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if (this.heap[leftIndex] < this.heap[index]) { this.swap(leftIndex, index); this.shiftDown(leftIndex); } if (this.heap[rightIndex] < this.heap[index]) { this.swap(rightIndex, index); this.shiftDown(rightIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0); } peek() { return this.heap[0]; } size() { return this.heap.length; } } var findKthLargest = function(nums, k) { if (nums.length < k || k <= 0) return; const h = new MinHeap(); nums.forEach(item => { h.insert(item); if (h.size() > k) { h.pop(); }}); return h.peek(); }Copy the code
Complexity analysis:
- Time complexity: O(nlogk) : n is the length of the array, k is the size of the heap.
- Space complexity: O(n)
347. The first K high frequency elements
Ideas:
Method one:
- Use hash table to record the number of occurrences of all elements, and then sort according to the number, and finally take out the first K high-frequency elements
Code display:
Method 1: Use hash tables and sorting
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map();
nums.forEach(n => {
map.set(n, map.has(n) ? map.get(n) + 1 : 1);
});
const list = Array.from(map).sort((a, b) => b[1] - a[1]);
return list.slice(0, k).map(n => n[0]);
};
Copy the code
Because the first method uses sorting, so the best time complexity is O(nlogn), does not meet the question.
Method two: minimum heap
/** * @param {number[]} nums * @param {number} k * @return {number[]} */ class MinHeap { constructor() { this.heap = []; } swap(i1, i2) { [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; } getLeftIndex(i) { return i * 2 + 1; } getRightIndex(i) { return i * 2 + 2; } getParentIndex(i) { return ~~((i - 1) / 2); } shiftUp(i) { if (i === 0) return; const pIndex = this.getParentIndex(i); if (this.heap[pIndex] && this.heap[pIndex].value > this.heap[i].value) { this.swap(pIndex, i); this.shiftUp(pIndex); } } shiftDown(i) { const lIndex = this.getLeftIndex(i); const rIndex = this.getRightIndex(i); if (this.heap[lIndex] && this.heap[lIndex].value < this.heap[i].value) { this.swap(lIndex, i); this.shiftDown(lIndex); } if (this.heap[rIndex] && this.heap[rIndex].value < this.heap[i].value) { this.swap(rIndex, i); this.shiftDown(rIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0); } peek() { return this.heap[0]; } size() { return this.heap.length; } } var topKFrequent = function(nums, k) { const h = new MinHeap(); const map = new Map(); nums.forEach(n => { map.set(n, map.has(n) ? map.get(n) + 1 : 1); }); map.forEach((value, key) => { h.insert({value, key}); if (h.size() > k) { h.pop() } }); return h.heap.map(n => n.key); };Copy the code
Complexity analysis:
- Time complexity: O(nlogk)
- Space complexity: O(n)
Merge K ascending linked lists
Ideas:
-
The next node in a new list must be the smallest of k list headers. Consider using a minimum heap.
-
Build a minimal heap and insert the list heads into the heap in turn.
-
Pop the top of the heap to the output list and insert the new list head of the list with the top of the heap into the heap.
-
When all the heap elements pop up, the merge is complete.
Code display:
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
class MinHeap {
constructor() {
this.heap = [];
}
swap(i1, i2) {
[this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
getParentIndex(i) {
return ~~((i - 1) / 2);
}
shiftUp(i) {
if (i === 0) return;
const pIndex = this.getParentIndex(i);
if (this.heap[pIndex] && this.heap[pIndex].val > this.heap[i].val) {
this.swap(pIndex, i);
this.shiftUp(pIndex);
}
}
shiftDown(i) {
const lIndex = this.getLeftIndex(i);
const rIndex = this.getRightIndex(i);
if (this.heap[lIndex] && this.heap[lIndex].val < this.heap[i].val) {
this.swap(lIndex, i);
this.shiftDown(lIndex);
}
if (this.heap[rIndex] && this.heap[rIndex].val < this.heap[i].val) {
this.swap(rIndex, i);
this.shiftDown(rIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
if (this.size() === 1) return this.heap.shift();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.shiftDown(0);
return top;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
var mergeKLists = function(lists) {
const res = new ListNode(0);
const h = new MinHeap();
let p = res;
lists.forEach(l => {
if (l) h.insert(l);
});
while (h.size()) {
const n = h.pop();
p.next = n;
p = p.next;
if (n.next) h.insert(n.next);
}
return res.next;
};
Copy the code
Complexity analysis:
- Time complexity: O(nlogk)
- Space complexity: O(n)
Offer 40. Minimum number of k
Code display:
Method 1: maximum pile
class MaxHeap { constructor() { this.heap = []; } swap(i1, i2) { [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]; } getLeftIndex(i) { return i * 2 + 1; } getRightIndex(i) { return i * 2 + 2; } getParentIndex(i) { return ~~((i - 1) / 2); } shiftUp(index) { if (index === 0) return; const pIndex = this.getParentIndex(index); if (this.heap[pIndex] < this.heap[index]) { this.swap(pIndex, index); this.shiftUp(pIndex); } } shiftDown(index) { const lIndex = this.getLeftIndex(index); const rIndex = this.getRightIndex(index); if (this.heap[lIndex] > this.heap[index]) { this.swap(lIndex, index); this.shiftDown(lIndex); } if (this.heap[rIndex] > this.heap[index]) { this.swap(rIndex, index); this.shiftDown(rIndex); } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0); } peek() { return this.heap[0]; } size() { return this.heap.length; } } var getLeastNumbers = function(arr, k) { if (k === 0) return []; const h = new MaxHeap(); arr.forEach(n => { h.insert(n); if (h.size() > k) { h.pop(); }}); return h.heap; };Copy the code
Method two: Quicksort
var getLeastNumbers = function(arr, k) {
if (k === 0) return [];
const quickSort = (arr) => {
if (arr.length <= 1) { return arr; }
const val = arr[0];
const leftArr = [], rightArr = [];
for (let i = 1; i < arr.length; i++) {
if (val < arr[i]) {
rightArr.push(arr[i]);
} else {
leftArr.push(arr[i]);
}
}
return [...quickSort(leftArr), val, ...quickSort(rightArr)];
}
return quickSort(arr).slice(0, k)
}
Copy the code
Method 3: Sort
var getLeastNumbers = function(arr, k) {
return arr.sort((a, b) => a - b).slice(0, k);
}
Copy the code
Complexity analysis:
- Time complexity: O(nlogk)
- Space complexity: O(n)
conclusion
The heap can solve this kind of problem for the first n smallest or largest elements, with better time complexity.