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 kindComplete binary tree.
  • All the nodes areGreater than or equal to (maximum heap)orLess than or equal to (minimum heap)Its children.
  • JS is commonly usedAn array ofSaid the heap.
  • On the leftsideChild nodesThe position is2 * index + 1.
  • rightsideChild nodesThe position is2 * index + 2.
  • The parent nodeThe 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 thekThe 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 thekThe 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.