简介

优先队列类似队列，在尾部插入元素，在头部移除元素。不同的是优先队列内的元素有优先级，移除的是优先级最大的元素。内部实现方式是堆(heap)，大顶堆或小顶堆。

堆(heap)是一种用数组实现的一种完全二叉树结构，节点是数组元素，父子节点之间的关系用数组下标来关联。以大顶堆为例，其父节点的值大于等于其子节点的值，小顶堆则相反。
优先队列(堆) - 图1

元素 10 7 2 5 1
下标 0 1 2 3 4

数组下标从0开始，对于元素 i，左孩子为元素 2*i+1, 右孩子为元素2*i + 2。

堆的构建时间复杂度为优先队列(堆) - 图2，插入和删除操作时间复杂度都为 优先队列(堆) - 图3

实现

  1. pub struct Heap {
  3. }
  5. impl Heap {
  6.      fn new() -> Self {
  8.     }
  10.     // 插入
  11.     fn push(&mut self, val: i32) {
  13.     }
  15.     // 删除
  16.     fn pop(&mut self) -> Option<i32> {
  18.     }
  20.     // 堆顶元素
  21.     fn top(&mut self) -> Option<i32> {
  23.     }
  24. }

例题

前 K 个高频元素