介绍

最小优先级队列是一种数据结构，它管理一个键（值）的列表。并且给具有最小值的元素以优先权。可以用 Heap 来实现它。

最小优先队列实际就是一个小顶堆，即每次插入堆中的元素，都存储至堆末端，通过上浮操作比较，小于父节点则和父节点交换元素，直到根结点为止，这样就形成了一个小顶堆。在获取最小值时，由于堆是数组的结构，只需获取根结点的值，即数组下标为 1 的值即可。获取最小值并删除，则可以交换根结点和尾结点，之后删除尾结点，并对根结点进行下沉操作，保证每个父节点都小于两个左右子树即可。

它支持以下操作：

• getMin () - 给出最小优先级的元素，但不要删除它。
• extractMin () - 给出最小优先级的元素，并删除它。
• insert (element) - 在优先级队列中插入一个元素。
• decrement (index, newValue) - 从优先级队列中减少一个元素。

为什么不使用其他数据结构（除了 Heap）？

• 链表：每次有新的元素出现将最小的元素放在顶部，或者一个元素的优先级改变时，运行时间复杂度为 O (n^2)。
• 二叉搜索树（Binary Search Tree）的插入很容易，获得最小值是一个简单的操作。它消耗了额外的空间来保存每个节点的指针。在插入和改变优先级的情况下，树需要再次被重新平衡，这比维护堆数据结构中的最小堆更复杂。堆使用数组，所以访问一个元素，缓存一个元素，总是更快的操作。

实现

JavaScript

const { Heap, MinHeap } = require('@datastructures-js/heap');

const getMinCompare = (getCompareValue) => (a, b) => {
  const aVal = typeof getCompareValue === 'function' ? getCompareValue(a) : a;
  const bVal = typeof getCompareValue === 'function' ? getCompareValue(b) : b;
  return aVal < bVal ? -1 : 1;
};

/**
 * @class MinPriorityQueue
 */
class MinPriorityQueue {
  constructor(getCompareValue, _heap) {
    if (getCompareValue && typeof getCompareValue !== 'function') {
      throw new Error('MinPriorityQueue constructor requires a callback for object values');
    }
    this._heap = _heap || new MinHeap(getCompareValue);
  }

  /**
   * Returns an element with highest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  front() {
    return this._heap.root();
  }

  /**
   * Returns an element with lowest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  back() {
    return this._heap.leaf();
  }

  /**
   * Adds a value to the queue
   * @public
   * @param {number|string|object} value
   * @returns {MinPriorityQueue}
   */
  enqueue(value) {
    return this._heap.insert(value);
  }

  /**
   * Removes and returns an element with highest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  dequeue() {
    return this._heap.extractRoot();
  }

  /**
   * Returns the number of elements in the queue
   * @public
   * @returns {number}
   */
  size() {
    return this._heap.size();
  }

  /**
   * Checks if the queue is empty
   * @public
   * @returns {boolean}
   */
  isEmpty() {
    return this._heap.isEmpty();
  }

  /**
   * Clears the queue
   * @public
   */
  clear() {
    this._heap.clear();
  }

  /**
   * Returns a sorted list of elements from highest to lowest priority
   * @public
   * @returns {array}
   */
  toArray() {
    return this._heap.clone().sort().reverse();
  }

  /**
   * Creates a priority queue from an existing array
   * @public
   * @static
   * @returns {MinPriorityQueue}
   */
  static fromArray(values, getCompareValue) {
    const heap = new Heap(getMinCompare(getCompareValue), values);
    return new MinPriorityQueue(
      getCompareValue,
      new MinHeap(getCompareValue, heap).fix()
    );
  }
}

或者：

/* Minimum Priority Queue
* It is a part of heap data structure
* A heap is a specific tree based data structure
* in which all the nodes of tree are in a specific order.
* that is the children are arranged in some
* respect of their parents, can either be greater
* or less than the parent. This makes it a min priority queue
* or max priority queue.
*/

// Functions: insert, delete, peek, isEmpty, print, heapSort, sink

class MinPriorityQueue {
  // calls the constructor and initializes the capacity
  constructor (c) {
    this.heap = []
    this.capacity = c
    this.size = 0
  }

  // inserts the key at the end and rearranges it
  // so that the binary heap is in appropriate order
  insert (key) {
    if (this.isFull()) return
    this.heap[this.size + 1] = key
    let k = this.size + 1
    while (k > 1) {
      if (this.heap[k] < this.heap[Math.floor(k / 2)]) {
        const temp = this.heap[k]
        this.heap[k] = this.heap[Math.floor(k / 2)]
        this.heap[Math.floor(k / 2)] = temp
      }
      k = Math.floor(k / 2)
    }
    this.size++
  }

  // returns the highest priority value
  peek () {
    return this.heap[1]
  }

  // returns boolean value whether the heap is empty or not
  isEmpty () {
    return this.size === 0
  }

  // returns boolean value whether the heap is full or not
  isFull () {
    if (this.size === this.capacity) return true
    return false
  }

  // prints the heap
  print (output = value => console.log(value)) {
    output(this.heap.slice(1))
  }

  // heap reverse can be done by performing swapping the first
  // element with the last, removing the last element to
  // new array and calling sink function.
  heapReverse () {
    const heapSort = []
    while (this.size > 0) {
      // swap first element with last element
      [this.heap[1], this.heap[this.size]] = [this.heap[this.size], this.heap[1]]
      heapSort.push(this.heap.pop())
      this.size--
      this.sink()
    }
    // first value from heap it's empty to respect
    // structure with 1 as index of the first element
    this.heap = [undefined, ...heapSort.reverse()]
    this.size = heapSort.length
  }

  // this function reorders the heap after every delete function
  sink () {
    let k = 1
    while (2 * k <= this.size || 2 * k + 1 <= this.size) {
      let minIndex
      if (this.heap[2 * k] >= this.heap[k]) {
        if (2 * k + 1 <= this.size && this.heap[2 * k + 1] >= this.heap[k]) {
          break
        } else if (2 * k + 1 > this.size) {
          break
        }
      }
      if (2 * k + 1 > this.size) {
        minIndex = this.heap[2 * k] < this.heap[k] ? 2 * k : k
      } else {
        if (
          this.heap[k] > this.heap[2 * k] ||
          this.heap[k] > this.heap[2 * k + 1]
        ) {
          minIndex =
            this.heap[2 * k] < this.heap[2 * k + 1] ? 2 * k : 2 * k + 1
        } else {
          minIndex = k
        }
      }
      const temp = this.heap[k]
      this.heap[k] = this.heap[minIndex]
      this.heap[minIndex] = temp
      k = minIndex
    }
  }

  // deletes the highest priority value from the heap. The last
  // element goes to ahead to first position and reorder heap
  delete () {
    // checks empty and one element array conditions
    if (this.isEmpty()) return
    if (this.size === 1) {
      this.size--
      return this.heap.pop()
    }
    const min = this.heap[1]
    this.heap[1] = this.heap.pop()
    this.size--
    this.sink()
    return min
  }
}