preface
In javaScript, all data structures are constructed from array objects, and the heap is constructed from array objects [], which is a complete binary tree structure in nature
JS heap: find node location, write, insert, delete, find, replace and other methods
Node location and heap use
1. Node position
- Position of left child node: 2 * index + 1
- Position of the child node on the right: 2 * index + 2
- Location of the parent node: (index-1) / 2. (i-1) >> 1 can be represented by a bit operation
2, the use of heap
- Quick finding of Max and min values, time complexity O(1)
- Find the KTH largest element
Minimum heap classes and methods
1. Build the minimum heap class
Insert involves moving the parent element, getParentIndex(I) to get the parent, upShift(index) to move the current node, and swap(i1,i2) to swap the value of the position.
// Build the minimum heap class
class MinHeap {
constructor() {
this.heap = []
}
/ / exchange
swap(i1, i2) {
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
// Get the parent node location
getParentIndex(i) {
return (i - 1) > >1
}
// Get the left child node position
getLeftIndex(i) {
return 2 * i + 1
}
// Get the right child node position
getRightIndex(i) {
return 2 * i + 2
}
/ / up
upShift(index) {
if(index == 0) return
const parentIndex = this.getParentIndex(index)
if(this.heap[parentIndex] > this.heap[index]) {
this.swap(index, parentIndex)
this.upShift(parentIndex)
}
}
/ / move down
downShift(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if(this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index)
this.downShift(leftIndex)
}
if(this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index)
this.downShift(rightIndex)
}
}
/ / insert
insert(value) {
this.heap.push(value)
this.upShift(this.heap.length - 1)}// Delete the heap top
pop() {
this.heap[0] = this.heap.pop()
this.downShift(0)}}Copy the code2. Insert method
According to the structure of the minimum heap, the insertion time complexity is O (logk),
/ / insert
insert(value) {
this.heap.push(value)
this.upShift(this.heap.length - 1)}Copy the codeTest insert method
let minheap = new MinHeap()
minheap.insert(6)
minheap.insert(2)
minheap.insert(3)
minheap.insert(1)
console.log(minheap.heap);
Copy the codeThe results of
3. Delete the heap top
- Replace the top of the heap with an element at the end of the array (removing the top directly breaks the heap structure)
- Move down: Swap the new heap top with its children until the children are greater than or equal to the new heap top
- The time complexity for removing a heap top from a heap top of size K is O (logk), the same as for inserting
GetLeftIndex (I), getRightIndex(I), downShift(index), swap(i1,i2)
// Delete the heap top
/** this.heap[0] the top value of the heap * this.heap. Pop () the value of the element at the end of the array */
pop() {
this.heap[0] = this.heap.pop()
this.downShift(0)}Copy the code- verify
let minheap = new MinHeap()
minheap.insert(6)
minheap.insert(2)
minheap.insert(3)
minheap.insert(1)
minheap.pop()
console.log(minheap.heap);
Copy the codeResults:
4. Get the heap top and heap size vscode debugging
These are simpler, returning the first element and the length of the array
// Get the heap top
peek() {
return this.heap[0]}// Get the heap size
size() {
return this.heap.length
}
Copy the code- You can view variable methods and so on in VS Code using node.js debugging environment, which can listen for peek() and size()
- F5 Starts debugging
- Step debugging in the call stack column
- Set breakpoint listening in the monitor column
Heap in LeetCode algorithm
The following algorithm is implemented on the basis of our above heap class
The KTH largest element in array 215
let findKLargest = function (nums, k) {
// Create a heap instance
const heap = new MinHeap()
for(let num of nums) {
// Insert the values of the array into the heap
heap.insert(num)
// Determine whether the heap capacity exceeds k
if (heap.size() > k) {
// If so, delete the heap top
heap.pop()
}
}
// return to the top of the heap
return heap.peek()
}
let arr1 = [3.2.1.5.6.4]
let arr2 = [3.2.2.1.2.4.5.5.6]
console.log(findKLargest(arr1, 2)); / / 5
console.log(findKLargest(arr2, 4)); / / 4
Copy the code- Time complexity: O (n*logK)
- Space complexity: O (logK)
2. 347. The first K high-frequency elements
Non-heap structure algorithm implementation k <= n
let topKFrequent = function (nums, k) {
const map = new Map(a);for(let n of nums) {
map.set(n, map.has(n) ? map.get(n) + 1 : 1)}const list = Array.from(map).sort((a, b) = > b[1] - a[1])
console.log(list.slice(0, k));
return list.slice(0, k).map(n= > n[0])}let arr3 = [1.1.1.2.2.3]
console.log(topKFrequent(arr3, 2));/ / [1, 2]
console.log(topKFrequent([1].1)); / / [1]
Copy the code- Time complexity: O (n*log n)
- Space complexity: O (log N)
Implementation of heap structure… The following minimum heap class is consistent with the comparison of the value of the object when it is passed in, so it is only modified in the if judgment of the method of up and down, which is to determine whether the parent, left and right nodes exist, respectively. Because the value inside is to be taken to prevent error when undefined, the rest of the class is not modified. It’s all taped up for easy reading
if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value)
if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value)
if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value)
Copy the codeThe algorithm and output of the heap class and topic are as follows:
class MinHeap {
constructor() {
this.heap = []
}
/ / exchange
swap(i1, i2) {
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
// Get the parent node location
getParentIndex(i) {
return (i - 1) > >1
}
// Get the left child node position
getLeftIndex(i) {
return 2 * i + 1
}
// Get the right child node position
getRightIndex(i) {
return 2 * i + 2
}
/ / up
upShift(index) {
if(index == 0) return
const parentIndex = this.getParentIndex(index)
if(this.heap[parentIndex]&& this.heap[parentIndex].value > this.heap[index].value) {
this.swap(index, parentIndex)
this.upShift(parentIndex)
}
}
/ / move down
downShift(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
this.swap(leftIndex, index)
this.downShift(leftIndex)
}
if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
this.swap(rightIndex, index)
this.downShift(rightIndex)
}
}
/ / insert
insert(value) {
this.heap.push(value)
this.upShift(this.heap.length - 1)}// Delete the heap top
pop() {
this.heap[0] = this.heap.pop()
this.downShift(0)}// Get the heap top
peek() {
return this.heap[0]}// Get the heap size
size() {
return this.heap.length
}
}
let topKFrequent = function (nums, k) {
const map = new Map(a);for(let n of nums) {
map.set(n, map.has(n) ? map.get(n) + 1 : 1)}const heap = new MinHeap()
map.forEach((value, key) = > {
heap.insert({value, key})
if(heap.size() > k) {
heap.pop()
}
})
return heap.heap.map(a= > a.key)
}
let arr3 = [1.1.1.2.2.3]
console.log(topKFrequent(arr3, 2));/ / (2, 1)
console.log(topKFrequent([1].1)); / / [1]
Copy the codeNote: there is no requirement for the order of output, as compared to non-heap structures.
- Time complexity: O (n*logK)
- Space complexity: O (logK)
Merge K sorted linked lists
- The next node in a new list must be the minimum of K list head weights
The problem solving steps
// Build the minimum heap class
class MinHeap {
constructor() {
this.heap = []
}
/ / exchange
swap(i1, i2) {
let temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
// Get the parent node location
getParentIndex(i) {
return (i - 1) > >1
}
// Get the left child node position
getLeftIndex(i) {
return 2 * i + 1
}
// Get the right child node position
getRightIndex(i) {
return 2 * i + 2
}
/ / up
upShift(index) {
if(index == 0) return
const parentIndex = this.getParentIndex(index)
if(this.heap[parentIndex]&& this.heap[parentIndex].value > this.heap[index].value) {
this.swap(index, parentIndex)
this.upShift(parentIndex)
}
}
/ / move down
downShift(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
this.swap(leftIndex, index)
this.downShift(leftIndex)
}
if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
this.swap(rightIndex, index)
this.downShift(rightIndex)
}
}
/ / insert
insert(value) {
this.heap.push(value)
this.upShift(this.heap.length - 1)}// Delete the heap top
pop() {
if(this.size() === 1) return this.heap.shift()
const top = this.heap[0]
this.heap[0] = this.heap.pop()
this.downShift(0)
return top
}
// Get the heap top
peek() {
return this.heap[0]}// Get the heap size
size() {
return this.heap.length
}
}
function ListNode(value) {
this.value = value
this.next = null
}
let mergeKlists = function (lists) {
const res = new ListNode(0)
let p = res
const heap = new MinHeap()
lists.forEach(list= > {
if (list) {
heap.insert(list)
}
})
while (heap.size()){
const n = heap.pop()
p.next = n
p = p.next
if (n.next) {
heap.insert(n.next)
}
}
return res.next
}
let lists = [[1.4.5], [1.3.4], [2.6]]
console.log(mergeKlists(lists));
Copy the codeThis one is a little difficult
- Time complexity: O (n*logK)
- Space complexity: O (K)
6. The structure of the article is MD
@[TOC](<center>Title</center>)
<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1 < p style=" margin-top: 1em; margin-bottom: 1em; border:solid; width:100px; height:1px;" color=#000000 size=1"Word-wrap: break-word! Important; "> < span style =" max-width: 100%'宋体' color = black size = 5> < span style = "max-width: 100%; clear: both; min-height: 1em1.# #2.# #3.# #4.# #5.# #6.# the last ><font face="宋体" color = black size = 4>Last words for readersCopy the codeThe last
Heap is a general term for a special type of data structure in computer science. A heap is usually an array object that can be viewed as a complete binary tree.
A heap is essentially a complete binary tree. A heap is represented by an array in JS [],
That’s a lot of swastikas.
paraphrase
Heap is a general term for a special type of data structure in computer science. A heap is usually an array object that can be thought of as a tree. A heap always has the following properties: the value of a node in the heap is always no greater than or less than the value of its parent; The heap is always a complete binary tree. The heap with the largest root is called the maximum heap or the large root heap, and the heap with the smallest root is called the minimum heap or the small root heap. Common heap have binary heap, Fibonacci heap and so on. A heap is a nonlinear data structure, equivalent to a one-dimensional array, with two immediate successors. A heap is defined as follows: a sequence of N elements {k1,k2,ki… Kn} is called a heap if and only if the following relation is satisfied. (and) or (), () If the one-dimensional array corresponding to the sequence is regarded as a complete binary tree, then the meaning of heap indicates that the values of all non-terminal nodes in the complete binary tree are not greater than (or less than) the values of its left and right child nodes. Thus, if the sequence {k1,k2… Kn} is the heap, then the top element of the heap (or the root of the complete binary tree) must be the minimum (or maximum) of n elements in the sequence.
Algorithm thought
Values do not have to be inserted into the heap one by one, swapped to form the heap. If the left and right subtrees of a small root heap are already heaps, and the element name of the root is root, and the left and right children of the root heap are left and right, there are two possible cases: (1) root <= left and root <= right, the heap is complete; (2) root >= left or root >= right, root should swap with the smaller of the two children, resulting in a heap, unless root is still larger than one or both of its new children. In this case, we simply continue the process of “pulling down” root until we reach a layer that is smaller than its children, or it becomes a leaf.
