“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

A previous article showed you how to use priority queues in force links. This article mainly talks about the priority queue implementation process.

Queues and priority queues

  • contrast

  • A priority queue can be logically viewed as a heap, but can actually be implemented as an array

The heap

A heap is a kind of nonlinear structure. It can be regarded as an array or a complete binary tree. Generally speaking, a heap is actually a one-dimensional array maintained by using the structure of a complete binary tree

  • According to the characteristics of the heap can be divided into big top heap and small top heap

  • Big top heap: Each node has a value greater than or equal to the value of its left and right children

  • Small top heap: Each node has values less than or equal to those of its left and right children

Insert and delete operations for the heap

The heap is inserted and deleted in accordance with the nature of queues, inserting elements at the end of the heap and deleting elements at the beginning of the heap

  • Insert adjustment: Inserts elements at the end of the heap and adjusts them upwards

  • Remove adjustment: pop the top of the heap element, place the bottom of the heap element at the top of the heap, and then adjust it down

Heap sort

  1. Swap the top heap element with the bottom heap element
  2. Think of this as a heap top element pop-up operation
  3. Adjust the heap according to the strategy after the head pops up
  4. Repeat the above steps

Code implementation heap

  • instantiation
    • arrPassing in an array
    • cmpThe compare () function is used to compare elements and determine if two elements need to be swapped when adjusting. The compare object is not necessarily the element itself, but can also be an attribute in the object, so it can be flexible, such as redefining when instantiating the heapcmp = (a, b) => a.x < b.x, ifa.x < b.xIndicates that elements need to be swapped
class Heap {
  constructor(arr = [], cmp = (a, b) => a < b) {
    this.arr = arr // Implement the heap with arrays
    this.cmp = (a, b) = > cmp(a, b) // Compare functions
  }

  Return the length of the heap
  size() {
    return this.arr.length
  }

  // Return the top of the heap element
  top() {
    if (!this.size()) return null
    return this.arr[0]}}Copy the code
  • Instantiate while adjusting the heap
  constructor(arr = [], cmp = (a, b) => a < b) {
    this.arr = arr // Implement the heap with arrays
    this.cmp = (a, b) = > cmp(a, b) // Compare functions
    this.heapify() // Initialize to adjust the nature of the heap
  }
  // Initialize the adjustment
  heapify() {
    if (this.size() < 2) return
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i) // Iterate over each element and adjust upward}}Copy the code
  • Insert delete element
  // Insert elements
  push(val) {
    this.arr.push(val) // Heap tail insertion
    this.bubbleUp(this.size() - 1) // Adjust upward
  }
  // Pop up elements
  pop() {
    if (!this.size()) return null
    if (this.size() === 1) return this.arr.pop()
    var top = this.top()
    this.arr[0] = this.arr.pop() // The element at the bottom of the heap is swapped with the element at the top of the heap
    this.bubbleDown(0) // Adjust downward
    return top
  }
Copy the code
  • Now the big thing is how do you adjust up and down, the idea is to find the index values of the two elements that you want to swap, and then swap
    • The upward adjustment requires comparisonThe current elementandThe parent element
    • The downward adjustment is going to beThe current elementRespectively withAbout the childTo compare the
  // Adjust upward
  bubbleUp(index) {
    while (index) {
      const parentIndex = Math.floor((index - 1) / 2) // The parent of the current element
      if (this.cmp(this.arr[index], this.arr[parentIndex])) { // If the conditions are met, swap
        [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]]
        index = parentIndex
      } else { 
        // Indicates that no swap is needed to exit the loop in the correct position
        break}}}// Adjust downward
  bubbleDown(index) {
    const lastIndex = this.size() - 1 // Heap tail element
    while (index < lastIndex) { 
      let findIndex = index // Current element
      let leftIndex = index * 2 + 1 / / the left child
      let rightIndex = index * 2 + 2 / / right child
      // Compare with the left child
      if (leftIndex <= lastIndex && this.cmp(this.arr[leftIndex], this.arr[findIndex])) {
        findIndex = leftIndex
      }
      // Compare with the right child
      if (rightIndex <= lastIndex && this.cmp(this.arr[rightIndex], this.arr[findIndex])) {
        findIndex = rightIndex
      }
      // If the index to be swapped has been found
      if (findIndex > index) {
        // Swap elements
        [this.arr[findIndex], this.arr[index]] = [this.arr[index], this.arr[findIndex]]
        index = findIndex
      } else { 
        // Indicates that no swap is needed to exit the loop in the correct position
        break}}}Copy the code

The complete code

class Heap {
  constructor(arr = [], cmp = (a, b) => a < b) {
    this.arr = arr // Implement the heap with arrays
    this.cmp = (a, b) = > cmp(a, b) // Compare functions
    this.heapify() // Initialize to adjust the nature of the heap
  }

  // The length of the heap
  size() {
    return this.arr.length
  }

  // Return the top of the heap element
  top() {
    if (!this.size()) return null
    return this.arr[0]}// Initialize the adjustment
  heapify() {
    if (this.size() < 2) return
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i) // Iterate over each element and adjust upward}}// Insert elements
  push(val) {
    this.arr.push(val) // Heap tail insertion
    this.bubbleUp(this.size() - 1) // Adjust upward
  }

  // Pop up elements
  pop() {
    if (!this.size()) return null
    if (this.size() === 1) return this.arr.pop()
    var top = this.top()
    this.arr[0] = this.arr.pop() // The element at the bottom of the heap is swapped with the element at the top of the heap
    this.bubbleDown(0) // Adjust downward
    return top
  }

  // Adjust upward
  bubbleUp(index) {
    while (index) {
      const parentIndex = Math.floor((index - 1) / 2) // The parent of the current element
      if (this.cmp(this.arr[index], this.arr[parentIndex])) { // If the conditions are met, swap
        [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]]
        index = parentIndex
      } else { 
        // Indicates that no swap is needed to exit the loop in the correct position
        break}}}// Adjust downward
  bubbleDown(index) {
    const lastIndex = this.size() - 1 // Heap tail element
    while (index < lastIndex) { 
      let findIndex = index // Current element
      let leftIndex = index * 2 + 1 / / the left child
      let rightIndex = index * 2 + 2 / / right child
      // Compare with the left child
      if (leftIndex <= lastIndex && this.cmp(this.arr[leftIndex], this.arr[findIndex])) {
        findIndex = leftIndex
      }
      // Compare with the right child
      if (rightIndex <= lastIndex && this.cmp(this.arr[rightIndex], this.arr[findIndex])) {
        findIndex = rightIndex
      }
      // If the index to be swapped has been found
      if (findIndex > index) {
        // Swap elements
        [this.arr[findIndex], this.arr[index]] = [this.arr[index], this.arr[findIndex]]
        index = findIndex
      } else { 
        // Indicates that no swap is needed to exit the loop in the correct position
        break}}}}Copy the code

Algorithmic problem application

692. The first K high-frequency words

/ * * *@param {string[]} words
* @param {number} k
* @return {string[]}* /
var topKFrequent = function (words, k) {
 var map = new Map(a)// Count the number of occurrences of the word
 words.forEach(item= > {
   map.has(item) ? map.set(item, map.get(item) + 1) : map.set(item, 1)})// Maintain a small top heap of K elements, the K elements that occur most frequently
 var mapArr = [...map]
 var heap = new Heap(mapArr, (a, b) = > {
   if(a[1] > b[1]) {return a[1] > b[1]}else if(a[1] === b[1]) {return a[0] < b[0]}})var temp = []
 while (k) {
   temp.push(heap.pop())
   k--
 }

 var res = []
 temp.forEach(item= > {
   res.push(item[0])})return res
};
Copy the code

— end —