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

preface

If you do a lot of work on algorithms, and if you’re a front-end developer, you probably do it in Javascript, which may not be like C++ or Java where you have some encapsulated data structures, like stacks and queues, that need to be implemented manually. What many people don’t know is that the fastener actually provides some wheels for us to use.

  • This place is more hidden after clicking

  • The prompt box tells us that Licou already has a built-in lodash.js library, which should be more familiar with the library, not to repeat the details.
  • Let’s focus on the second priority queue

Heap and priority queue

Speaking of priority queues, we have to talk about the concept of heap first

The heap

  • 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.
  • The heap can be divided into large top (root) heap and small top (root) heap
  • Take the big top heap as an example: for any node, the root is required to be greater than or equal to the values of all its subtrees, while for a small top pair, the opposite is true

Priority queue

  • A normal queue is a first-in, first-out data structure, with elements appended at the end of the queue and removed from the head of the queue. In priority queues, elements are assigned priority. When an element is accessed, the element with the highest priority is deleted first. Priority queues have the behavior characteristics of first in (largest out). It is usually implemented using heap data structures.
  • In Javascript, the concept of a heap can be implemented using arrays. There will be a separate article on how to implement a heap yourself.
  • How to use priority-queue? The priority-queue document provided by Lico has been written in detail

Role of heap-priority queues

In a word: heap fit for maintenance: collection Max

Real operation force buckle algorithm

23. Merge K ascending linked lists

  • Analysis of the

If you use brute force, you have to iterate through the array every time, get the list with the smallest head, insert that value to the end of the new list, remove the head, put the list back into the array, and loop through the search again, so that no unexpected force will time out

If priority queues are used, each loop can obtain the list element with the smallest head node from the head of the queue. If the sum of the length of all lists is K, the spatial complexity of the algorithm is O(k).

  • Code implementation
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode[]} lists
 * @return {ListNode}* /
var mergeKLists = function(lists) {
    var heap = new MinPriorityQueue({ / / small cap pile
        priority: (bid) = > bid.val // The top of the heap is the list with the smallest head node
    })
    // Heap in sequence
    for(var list of lists) {
        if(! list)continue
        heap.enqueue(list)
    }
    var ret = new ListNode() // Virtual head node for easy return
    var p = ret / / pointer
    // Take the list one at a time from the top of the heap, link the top node to the end of the new list, and then shove it back into the heap
    while(heap.size()) {
        var cur = heap.dequeue().element // Pop up the top of the heap element
        p.next = cur
        p = p.next
        if(cur.next) heap.enqueue(cur.next) // If the list has not reached the end of the heap, put it back in the heap
    }
    p.next = null // The list ends with a pointer to null
    return ret.next
};
Copy the code

— end —