Captain emoticons town building
Heap: Usually an array object that can be viewed as a complete binary tree.
- Large top heap: the root node has the largest value, and any child node is smaller than the parent node
- Large top heap: the root node has the smallest value and any child node is larger than the parent node
- A complete binary tree can be represented by a contiguous segment of storage.
Tail insertion adjustment
- Big top heap: The inserted values are placed at the left of the last layer of the complete binary tree, or at the end of the array, and then compared to the parent or, if larger, swapped with the parent
- Small top heap: Inserted values are placed at the left of the last layer of the complete binary tree, or at the end of the array, and then compared to the parent or, if smaller, switched
Head pop-out adjustment
- Big top heap: Eject the root node and place the tail node on top of the root node, which will swap places with the larger child node until it conforms to the properties of the big top heap
- Big top heap: Eject the root node and place the tail node on top of the root node, which will swap positions with smaller child nodes until it conforms to the properties of the small top heap
Heap sort
With the big top heap, the top element pops up interchangeable with the bottom element, the second pops up interchangeable with the penultimate bottom element, and so on, resulting in an ordered array from smallest to largest
Heap and priority queue
A heap is an implementation of a priority queue
The core application
- Find the maximum value of the set
Data structure is divided into two parts, one is the structure definition, the other is the structure operation. Data structures are about defining a property and then maintaining that property
Use JS to manually tear a heap
class Heap {
constructor(data, type, compartor) {
this.data = data || []
// There is a default rule that can specify the type, passing less is the big top heap,
// If you pass in a custom comparison rule, type is invalid
this.compartor = compartor || function(a, b) {
if (type == 'less') return a - b
else return b - a
}
this.heapify()
}
size() {
return this.data.length
}
// Process the element order
heapify() {
if (this.size() < 2) {
return
}
for (let i = 1; i < this.size(); i++) {
this.bubbleUp(i)
}
}
// Get the top of the heap element
top() {
if (!this.size()) return null
return this.data[0]}// Add element operations
push(val) {
this.data.push(val)
this.bubbleUp(this.size() - 1)}// Pop up the top of the heap element
pop() {
if (!this.size()) return null
if (this.size() == 1) return this.data.pop()
let res = this.data[0]
this.data[0] = this.data.pop()
if (this.size()) {
this.bubbleDown(0)}return res
}
// Swap elements
swap(i, j) {
if (i === j) return
[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
}
// Adjust up to position 0
bubbleUp(index) {
while (index) {
// Get the parent of the current node,
const parenIndex = (index - 1) > >1;
// const parenIndex = Math.floor((index - 1) / 2);
// const parenIndex = (index - 1) / 2 | 0;
// Compare the value of the parent node with the current value.
if (this.compartor(this.data[index], this.data[parenIndex]) > 0) {
// Swap parent and child nodes
this.swap(index, parenIndex);
// Swap parent and child subscripts
index = parenIndex;
} else {
// Prevent dead loops.
break; }}}// Get the maximum subscript to ensure that no swap out of bounds.
bubbleDown(index) {
let lastIndex = this.size() - 1;
while (index < lastIndex) {
// Get the subscripts of the left and right sons
let leftIndex = index * 2 + 1;
let rightIndex = index * 2 + 2;
// Node to be switched
let findIndex = index;
if (leftIndex <= lastIndex
&& this.compartor(this.data[leftIndex], this.data[findIndex]) > 0) {
findIndex = leftIndex;
}
if (rightIndex <= lastIndex && this.compartor(this.data[rightIndex], this.data[findIndex]) > 0) {
findIndex = rightIndex;
}
if(index ! == findIndex) {this.swap(index, findIndex);
index = findIndex;
} else {
break; }}}}Copy the codeLeetCode liver questions (for training purposes)
- Offer 40. Minimum number of k
// Create a big top heap, if the heap length is greater than k, pop, the remaining is the minimum k number
var getLeastNumbers = function(arr, k) {
if (k == 0) return []
let h = new Heap(arr, 'less')
while(h.size() > k) h.pop()
return h.data;
};
Copy the code-
- The weight of the last stone
// Create a large top heap, subtracting the top elements of each heap until there is only one element left
var lastStoneWeight = function(stones) {
let h = new Heap(stones, 'less')
while(h.size() > 1) {
let big = h.pop(), small = h.pop()
if (big - small) h.push(big - small)
}
return h.top()
};
Copy the code-
- The KTH largest element in the data stream
// Create a small top heap. If the length of the heap is greater than k, the top element is the KTH element
var KthLargest = function(k, nums) {
this.h = new Heap(nums, 'greator')
this.k = k
};
KthLargest.prototype.add = function(val) {
this.h.push(val)
while(this.h.size() > this.k) this.h.pop()
return this.h.top()
};
Copy the code-
- Find and the smallest k-pair number
// Define a large top heap comparison rule that compares the sum of two items in array A and two items in array B
var compartor = function(a, b) {
return a[0] + a[1] - b[0] - b[1]}var kSmallestPairs = function(nums1, nums2, k) {
let h = new Heap([], 'less', compartor)
for(let i in nums1) {
for(let j in nums2) {
// Arrange all the numbers in the big top heap, compare the sum of any two numbers, and the smaller k group is saved in the big top heap
h.push([nums1[i], nums2[j]])
if(h.size() > k) h.pop()
}
}
return h.data
};
Copy the code-
- The KTH largest element in the array
// Create a small top heap. If the length of the heap is greater than k, the top element is the KTH element
var findKthLargest = function(nums, k) {
let h = new Heap(nums, 'greator')
while(h.size() > k) h.pop()
return h.top()
};
Copy the code-
- The first K high frequency words
// Define a small top heap comparison rule that compares the number of nodes and the priority of words
var topKFrequent = function(words, k) {
let obj = {}
// Count the number of occurrences of all words
for(let item of words) {
obj[item] = obj[item] + 1 || 1
}
// Custom comparison rules, when the number of times is not equal to the number of times to go up
// When the number of words is equal, compare the size of the words, i.e. the order of the words, and pop up the next word first
// When sort sort, a> B is in ascending order
let compartor = function(a, b) {
if(obj[a] == obj[b]) return a > b ? 1: -1
return obj[b] - obj[a]
}
let h = new Heap(Object.keys(obj), 'greator', compartor)
while(h.size() > k) h.pop()
h.data.sort(compartor)
return h.data
};
Copy the code-
- The median of the data stream
The first half of the data is represented by the big top heap, and the second half of the data is represented by the small top heap
// Set the first heap to have at most one element more than the second heap, otherwise adjust the number
// If the number of elements in the heap is equal, the median is the top element of the two heaps /2. If the number is not equal, it is the top element of the first heap
var MedianFinder = function() {
this.lessH = new Heap([], 'less')
this.greatorH = new Heap([], 'greator')};/ * * *@param {number} num
* @return {void}* /
MedianFinder.prototype.addNum = function(num) {
if (this.lessH.size() == 0 || num <= this.lessH.top()) {
this.lessH.push(num)
} else {
this.greatorH.push(num)
}
if(this.lessH.size() < this.greatorH.size()) {
this.lessH.push(this.greatorH.pop())
}
if (this.lessH.size() - this.greatorH.size() > 1) {
this.greatorH.push(this.lessH.pop())
}
};
/ * * *@return {number}* /
MedianFinder.prototype.findMedian = function() {
if (this.lessH.size() == this.greatorH.size()) {
return (this.lessH.top() + this.greatorH.top())/2
}
return this.lessH.top()
};
Copy the code-
- The number of ugly II
// Maintain a small top heap
var nthUglyNumber = function(n) {
let h = new Heap([1].'greator')
while(--n) {
// Retrieve the top element
let top = h.pop()
// Push top*5 if it is an integer multiple of 5
if (top % 5= = =0) {
h.push(top * 5)
// Push top*5 and top*3 if it is an integer multiple of 3
} else if (top % 3= = =0) {
h.push(top * 5)
h.push(top * 3)}else {// Otherwise all three are pushed into the heap to prevent the addition of duplicate elements
h.push(top * 5)
h.push(top * 3)
h.push(top * 2)}}return h.top()
};
Copy the code-
- Super ugly number
// Create an array p to record the position of the multiplier, and create an array data to record all ugly numbers
var nthSuperUglyNumber = function(n, primes) {
let p = new Array(primes.length).fill(0)
let data = [1], ans = 1
while(data.length < n) {
ans = primes[0] * data[p[0]]
// assign the minimum ugliness value to ans
for(let i = 1; i< primes.length; i++) {
ans = Math.min(ans, primes[i] * data[p[i]])
}
// Subscript all ugly numbers that can yield ANS +1, update coordinates and remove duplicate values
for(let i = 0; i< primes.length; i++) {
if(primes[i] * data[p[i]] === ans) p[i]++
}
data.push(ans)
}
return ans
};
Copy the code-
- The maximum score for removing stones
// A is the smallest, c is the largest
var maximumScore = function(a, b, c) {
let ans = 0
if (a > b) [a, b] = [b, a]
if (a > c) [a, c] = [c, a]
if (b > c) [b, c] = [c, b]
if (c - b > a) { // If the difference between B and C is greater than a, the final score is B + C
ans = b + a
} else { // Otherwise, the difference of BC cancels out A, then half of A cancels out B and C, respectively, and finally adds either b or C
ans = c - b
a -= ans
let i = a >> 1
b -= i
ans += i * 2
ans += b
}
return ans
};
Copy the code-
- Design of twitter
// Design a big top heap, compare the third time
// Create a set of users with key as user ID and value as concern list
// This problem uses the sorting set to simplify the answer, and will be optimized later
var cmp = function(a, b) {
return a[2] - b[2]}var Twitter = function() {
this.user = {}
this.twitter = new Heap([], 'less', cmp)
this.time = 0
};
// Send a tweet to the heap
Twitter.prototype.postTweet = function(userId, tweetId) {
this.twitter.push([userId, tweetId, this.time++])
};
// Follow, push the id of the user to be followed to the user's follow list
Twitter.prototype.follow = function(followerId, followeeId) {
this.user[followerId] ? this.user[followerId].push(followeeId) : this.user[followerId] = [followeeId]
};
// Remove the user ID from the user's focus list
Twitter.prototype.unfollow = function(followerId, followeeId) {
if (!this.user[followerId]) return
this.user[followerId].splice(this.user[followerId].findIndex(item= > item == followeeId), 1)};If the heap is empty, return an empty array. Design a Set to store it in the user and his concern list. If the top tweet id is in the Set, push the tweet into ANS, and return ANS
Twitter.prototype.getNewsFeed = function(userId) {
if(this.twitter.size() == 0) return []
let list = [...(this.user[userId]||[]), userId], ans = [], n = 10, data = JSON.parse(JSON.stringify(this.twitter.data))
let userSet = new Set(list)
while(n && this.twitter.size()) {
let top = this.twitter.pop()
if (userSet.has(top[0])) {
ans.push(top[1])
n--
}
}
this.twitter = new Heap(data, 'less', cmp)
return ans
};
Copy the code-
- Total number of orders in backlog
The first element is price, the second is quantity, the third is category, 0 is purchase order, and 1 is sales order
// Maintain two heaps, the buying heap is the big top heap, the sales heap is the small top heap, and the heap elements are an array, the first item is price, the second item is quantity
// Match the highest purchase price with the lowest sale price (the profiteer is done)
// Define the comparison rule between two heaps
var compartor1 = function(a, b) {
return a[0] - b[0]}var compartor2 = function(a, b) {
return b[0] - a[0]}var getNumberOfBacklogOrders = function(orders) {
let buy = new Heap([], 'less', compartor1), sell = new Heap([], 'greator', compartor2)
for(let x of orders) {
if (x[2] = =0) {
while (x[1] != 0 && sell.size() && sell.data[0] [0] <= x[0]) {
let cnt = Math.min(x[1], sell.data[0] [1])
x[1] -= cnt
sell.data[0] [1] -= cnt
if (sell.data[0] [1] = =0) sell.pop()
}
if (x[1] != 0) buy.push(x)
} else {
while (x[1] != 0 && buy.size() && buy.data[0] [0] >= x[0]) {
let cnt = Math.min(x[1], buy.data[0] [1])
x[1] -= cnt
buy.data[0] [1] -= cnt
if (buy.data[0] [1] = =0) buy.pop()
}
if (x[1] != 0) sell.push(x)
}
}
let mod = 1000000007, sum = 0
for(let item of buy.data) {
sum = (sum + item[1]) % mod
}
for(let item of sell.data) {
sum = (sum + item[1]) % mod
}
return sum
};
Copy the code