贪心算法，优先队列数据结构，自定义排序技巧，初始化整型为最大值，求解《857. 雇佣 K 名工人的最低成本》。总结 JavaScript / TypeScript / PHP / Golang / Java / C# / C++ / Python 的优先队列的使用（实现）方法。

class MyPriorityQueue {
  constructor (ar = [], compare = (a, b) => a - b) {
    this.heap = []
    this.size = 0
    this.compare = compare
    while (ar.length) this.push(ar.pop())
  }
  swap(a, b) {
    const t = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = t
  }
  getLeftIndex(index) {
    return (index << 1) + 1
  }
  getRightIndex(index) {
    return (index << 1) + 2
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
      this.swap(index, leftIndex)
      this.shiftDown(leftIndex)
    }
    if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
      this.swap(index, rightIndex)
      this.shiftDown(rightIndex)
    }
  }
  getParentIndex(index) {
    return index - 1 >> 1
  }
  shiftUp(index) {
    const paretIndex = this.getParentIndex(index)
    if (paretIndex >= 0 && this.compare(this.heap[paretIndex], this.heap[index]) > 0) {
      this.swap(paretIndex, index)
      this.shiftUp(paretIndex)
    }
  }
  push(value) {
    this.heap.push(value)
    this.shiftUp(this.size++)
  }
  top() {
    return this.heap[0]
  }
  pop() {
    if (this.size === 0) return null
    if (--this.size === 0) return this.heap.pop()
    const top = this.top()
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }
  empty() {
    return this.size === 0
  }
}

class MyPriorityQueue {
  #heap: number[]
  #size: number
  #compare: (a: number, b: number) => number
  constructor(ar: number[] = [], compare = (a: number, b: number): number => a - b) {
    this.#heap = []
    this.#size = 0
    this.#compare = compare
    while (ar.length) this.push(ar.pop())
  }
  swap(a: number, b: number) {
    const t = this.#heap[a]
    this.#heap[a] = this.#heap[b]
    this.#heap[b] = t
  }
  getParentIndex(index: number): number {
    return index - 1 >> 1
  }
  shiftUp(index: number) {
    const parentIndex = this.getParentIndex(index)
    if (parentIndex >= 0 && this.heap[parentIndex], this.#heap[index]) > 0) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }
  getLeftChildIndex(index: number): number {
    return (index << 1) + 1
  }
  getRightChildIndex(index: number): number {
    return (index << 1) + 2
  }
  shiftDown(index: number) {
    const leftChildIndex = this.getLeftChildIndex(index)
    const rightChildIndex = this.getRightChildIndex(index)
    if (leftChildIndex < this.#size && this.heap[index], this.#heap[leftChildIndex]) > 0) {
      this.swap(index, leftChildIndex)
      this.shiftDown(leftChildIndex)
    }
    if (rightChildIndex < this.#size && this.heap[index], this.#heap[rightChildIndex]) > 0) {
      this.swap(index, rightChildIndex)
      this.shiftDown(rightChildIndex)
    }
  }
  push(value: number) {
    this.#heap.push(value)
    this.shiftUp(this.#size++)
  }
  top(): number { // peak
    return this.#heap[0]
  }
  pop(): number {
    if (this.#size == 0) return null
    if (--this.#size == 0) return this.#heap.pop()
    const top = this.top()
    this.#heap[0] = this.#heap.pop()
    this.shiftDown(0)
    return top
  }
  size(): number {
    return this.#size
  }
  empty(): boolean {
    return this.size() === 0
  }
}

type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 小根堆
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}
// 使用
hp := &IntHeap{}
heap.Init(hp)
heap.Push(hp, x)
heap.Pop().(int)

class PriorityQueue extends SplPriorityQueue {
  public function compare ($a, $b) {
    f ($a === $b) {
      return 0;
    }
    return $a < $b ? -1 : 1; // 大根堆
  }
}
class SplPriorityQueue implements Iterator, Countable {
  public compare(mixed $priority1, mixed $priority2): int
  public count(): int
  public current(): mixed
  public extract(): mixed
  public getExtractFlags(): int
  public insert(mixed $value, mixed $priority): bool
  public isCorrupted(): bool
  public isEmpty(): bool
  public key(): int
  public next(): void
  public recoverFromCorruption(): bool
  public rewind(): void
  public setExtractFlags(int $flags): int
  public top(): mixed
  public valid(): bool
}

PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
/** Methods */
boolean add(E e)
// Inserts the specified element into this priority queue.
void    clear()
// Removes all of the elements from this priority queue.
Comparator<? super E>   comparator()
// Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.
boolean contains(Object o)
// Returns true if this queue contains the specified element.
Iterator<E> iterator()
// Returns an iterator over the elements in this queue.
boolean offer(E e)
// Inserts the specified element into this priority queue.
E   peek()
// Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E   poll()
// Retrieves and removes the head of this queue, or returns null if this queue is empty.
boolean remove(Object o)
// Removes a single instance of the specified element from this queue, if it is present.
int size()
// Returns the number of elements in this collection.
Object[]    toArray()
// Returns an array containing all of the elements in this queue.
<T> T[] toArray(T[] a)
// Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

PriorityQueue<int> q = new PriorityQueue<int>((a, b) -> b - a); // 大根堆
/** Method */
Clear() 
// Removes all items from the PriorityQueue<TElement,TPriority>.
Dequeue()   
// Removes and returns the minimal element from the PriorityQueue<TElement,TPriority> - that is, the element with the lowest priority value.
Enqueue(TElement, TPriority)    
// Adds the specified element with associated priority to the PriorityQueue<TElement,TPriority>.
EnqueueDequeue(TElement, TPriority) 
// Adds the specified element with associated priority to the PriorityQueue<TElement,TPriority>, and immediately removes the minimal element, returning the result.
Peek()  
// Returns the minimal element from the PriorityQueue<TElement,TPriority> without removing it.

priority_queue q; // 大根堆
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
empty() // Test whether container is empty (public member function)
size() // Return size (public member function)
top() // Access top element (public member function)
push() // Insert element (public member function)
emplace() // Construct and insert element (public member function)
pop() // Remove top element (public member function)
swap() // Swap contents (public member function)

heapq.heappush(heap, item)
# 将 item 的值加入 heap 中，保持堆的不变性。

heapq.heappop(heap)¶
# 弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。

heapq.nlargest(n, iterable, key=None)
# 从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key, reverse=True)[:n]。

heapq.nsmallest(n, iterable, key=None)
# 从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]。

var mincostToHireWorkers = function(quality, wage, k) { // 使用第三方类
  const q = new MaxPriorityQueue(), n = quality.length
  const is = Array.from({length: n}, (_, i) => i).sort((a, b) => wage[a] * quality[b] - wage[b] * quality[a])
  let r = Number.MAX_SAFE_INTEGER, total = 0
  for (let i = 0; i < n; i++) {
    total += quality[is[i]]
    q.enqueue(quality[is[i]])
    if (i < k - 1) continue
    r = Math.min(r, total * wage[is[i]] / quality[is[i]])
    total -= q.dequeue().element
  }
  return r
};

var mincostToHireWorkers = function(quality, wage, k) {  // 自行实现
  const q = new MyPriorityQueue([], (a, b) => b - a), n = quality.length
  const is = Array.from({length: n}, (_, i) => i)
  is.sort((a, b) => wage[a] * quality[b] - wage[b] * quality[a])
  let r = Number.MAX_SAFE_INTEGER, total = 0
  for (let i = 0; i < k - 1; i++) {
    total += quality[is[i]]
    q.push(quality[is[i]])
  }
  for (let i = k - 1; i < n; i++) {
    total += quality[is[i]]
    q.push(quality[is[i]])
    r = Math.min(r, total * wage[is[i]] / quality[is[i]])
    total -= q.pop()
  }
  return r
};
class MyPriorityQueue {
  constructor (ar = [], compare = (a, b) => a - b) {
    this.heap = []
    this.size = 0
    this.compare = compare
    while (ar.length) this.push(ar.pop())
  }
  swap(a, b) {
    const t = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = t
  }
  getLeftIndex(index) {
    return (index << 1) + 1
  }
  getRightIndex(index) {
    return (index << 1) + 2
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
      this.swap(index, leftIndex)
      this.shiftDown(leftIndex)
    }
    if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
      this.swap(index, rightIndex)
      this.shiftDown(rightIndex)
    }
  }
  getParentIndex(index) {
    return index - 1 >> 1
  }
  shiftUp(index) {
    const paretIndex = this.getParentIndex(index)
    if (paretIndex >= 0 && this.compare(this.heap[paretIndex], this.heap[index]) > 0) {
      this.swap(paretIndex, index)
      this.shiftUp(paretIndex)
    }
  }
  push(value) {
    this.heap.push(value)
    this.shiftUp(this.size++)
  }
  top() {
    return this.heap[0]
  }
  pop() {
    if (this.size === 0) return null
    if (--this.size === 0) return this.heap.pop()
    const top = this.top()
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }
  empty() {
    return this.size === 0
  }
}

function mincostToHireWorkers(quality: number[], wage: number[], k: number): number { // 使用第三方类
  const q = new MaxPriorityQueue(), n = quality.length
  const h = Array.from({length: n}, (_, i) => i).sort((a, b) => wage[a] * quality[b] - wage[b] * quality[a])
  let r = Number.MAX_SAFE_INTEGER, total = 0
  for (let i = 0; i < n; i++) {
    total += quality[h[i]]
    q.enqueue(quality[h[i]])
    if (i < k - 1) continue
    r = Math.min(r, total * wage[h[i]] / quality[h[i]])
    total -= q.dequeue().element
  }
  return r
};

function mincostToHireWorkers(quality: number[], wage: number[], k: number): number { // 自行实现
  const q: MyPriorityQueue = new MyPriorityQueue([], (a, b) => b - a), n = quality.length
  const h = Array.from({length: n}, (_, i) => i).sort((a, b) => wage[a] * quality[b] - wage[b] * quality[a])
  let r = Number.MAX_SAFE_INTEGER, total = 0
  for (let i = 0; i < n; i++) {
    total += quality[h[i]]
    q.push(quality[h[i]])
    if (i < k - 1) continue
    r = Math.min(r, total * wage[h[i]] / quality[h[i]])
    total -= q.pop()
  }
  return r
};
class MyPriorityQueue {
  #heap: number[]
  #size: number
  #compare: (a: number, b: number) => number
  constructor(ar: number[] = [], compare = (a: number, b: number): number => a - b) {
    this.#heap = []
    this.#size = 0
    this.#compare = compare
    while (ar.length) this.push(this.#heap.pop())
  }

  swap(a: number, b: number) {
    const t = this.#heap[a]
    this.#heap[a] = this.#heap[b]
    this.#heap[b] = t
  }

  getLeftIndex(index: number): number {
    return (index << 1) + 1
  }

  getRightIndex(index: number): number {
    return (index << 1) + 2
  }

  shiftDown(index: number) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (leftIndex < this.#size && this.heap[index], this.#heap[leftIndex]) > 0) {
      this.swap(index, leftIndex)
      this.shiftDown(leftIndex)
    }
    if (rightIndex < this.#size && this.heap[index], this.#heap[rightIndex]) > 0) {
      this.swap(index, rightIndex)
      this.shiftDown(rightIndex)
    }
  }

  getParentIndex(index: number): number {
    return index - 1 >> 1
  }

  shiftUp(index: number) {
    const parentIndex = this.getParentIndex(index)
    while (parentIndex >= 0 && this.heap[parentIndex], this.#heap[index]) > 0) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  push(value: number) {
    this.size] = value
    this.shiftUp(this.#size++)
  }

  top(): number {
    return this.#heap[0]
  }

  pop(): number {
    if (this.#size === 0) return null
    if (--this.#size === 0) return this.#heap[0]
    const top = this.top()
    this.#heap[0] = this.#heap.pop()
    this.shiftDown(0)
    return top
  }

  size(): number {
    return this.#size
  }

  empty(): boolean {
    return this.#size === 0
  }
}

import "container/heap"
func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
  hp, n, r := &IntHeap{}, len(quality), float64(^uint(0) >> 1)
  heap.Init(hp)
  is := make([]int, n)
  for i := 0; i < n; i++ {
    is[i] = i
  }
  sort.Slice(is, func(i, j int) bool {
    a, b := is[i], is[j]
    return wage[a] * quality[b] < wage[b] * quality[a]
  })
  total := 0
  for i, v := range is {
    total += quality[v]
    heap.Push(hp, quality[v])
    if i < k - 1 {
      continue
    }
    r = math.Min(r, float64(total) * float64(wage[v]) / float64(quality[v]))
    total -= heap.Pop(hp).(int)
  }
  return r
}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // 大根堆
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
  old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

class Solution {
  function mincostToHireWorkers($quality, $wage, $k) {
    $q = new PriorityQueue();
    $q->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
    $n = count($quality);
    $is = array_fill(0, $n, 0);
    for ($i = 0; $i < $n; $i++) $is[$i] = $i;
    usort($is, fn($a, $b) => $wage[$a] / $quality[$a] > $wage[$b] / $quality[$b]);
    $total = 0;
    $r = PHP_INT_MAX;
    foreach ($is as $i => $v) {
      $total += $quality[$v];
      $q->insert(null, $quality[$v]);
      if ($i < $k - 1) continue;
      $r = min($r, $total * $wage[$v] / $quality[$v]);
      $total -= $q->extract();
    }
    return $r;
  }
}
class PriorityQueue extends SplPriorityQueue {
  public function compare ($a, $b) {
    f ($a === $b) {
      return 0;
    }
    return $a < $b ? -1 : 1; // 大根堆
  }
}

class Solution {
  public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
    int n = quality.length, total = 0;
    double r = Integer.MAX_VALUE;
    Integer[] is = new Integer[n];
    for (int i = 0; i < n; i++) is[i] = i;
    Arrays.sort(is, (a, b) -> wage[a] * quality[b] - wage[b] * quality[a]);
    for (int i = 0; i < n; i++) {
      total += quality[is[i]];
      q.offer(quality[is[i]]);
      if (i < k - 1) continue;
      r = Math.min(r, total * (double) wage[is[i]] / quality[is[i]]);
      total -= q.poll();
    }
    return r;
  }
}

public class Solution {
  public double MincostToHireWorkers(int[] quality, int[] wage, int k) {
    PriorityQueue<int, int> q = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
    int n = quality.Length, total = 0;
    int[] list = new int[n];
    for (int i = 0; i < n; i++) list[i] = i;
    Array.Sort(list, (a, b) => wage[a] * quality[b] - wage[b] * quality[a]);
    double r = int.MaxValue;
    for (int i = 0; i < n; i++) {
      total += quality[list[i]];
      q.Enqueue(quality[list[i]], quality[list[i]]);
      if (i < k - 1) continue;
      r = Math.Min(r, total * (double) wage[list[i]] / quality[list[i]]);
      total -= q.Dequeue();
    }
    return r;
  }
}

class Solution {
public:
  double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
    priority_queue<int> q;
    int n = quality.size(), total = 0;
    vector<int> h(n);
    for (int i = 0; i < n; i++) h[i] = i;
    sort(h.begin(), h.end(), [&quality, &wage](int& a, int& b) {
      return quality[a] * wage[b] > quality[b] * wage[a];
    });
    double r = INT_MAX;
    for (int i = 0; i < n; i++) {
      total += quality[h[i]];
      q.push(quality[h[i]]);
      if (i < k - 1) continue;
      r = min(r, total * (double) wage[h[i]] / quality[h[i]]);
      total -= q.top();
      q.pop();
    }
    return r;
  }
};

class Solution(object):
  def mincostToHireWorkers(self, quality, wage, k): # Python 2.7.12
    q, n, total, r = [], len(quality), 0, sys.maxint # sys.maxint
    h = [i for i in range(0, n)]
    h.sort(cmp = lambda a, b: wage[a] * quality[b] - wage[b] * quality[a]) # cmp
    for i, v in enumerate(h):
      total += quality[v]
      heappush(q, -quality[v])
      if i < k - 1: continue
      r = min(r, total * float(wage[v]) / quality[v])
      total -= -heappop(q)
    return r

class Solution:
  def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float: # Python 3.10
    q, n, total, r = [], len(quality), 0, sys.maxsize # sys.maxsize
    h = [i for i in range(0, n)]
    h.sort(key = lambda v: float(wage[v]) / quality[v]) # key
    for i, v in enumerate(h):
      total += quality[v]
      heappush(q, -quality[v])
      if i < k - 1: continue
      r = min(r, total * float(wage[v]) / quality[v])
      total -= -heappop(q)
    return r