【数据结构】堆，优先级队列

目录

• 一、堆
• 二、堆的性质
• 三、大根堆的模拟实现
• • 3.1 接口实现
  • 3.2 构造方法
  • 3.3 建堆
  • 3.4 入堆
  • 3.5 判满
  • 3.6 删除
  • 3.7 判空
  • 3.8 获取堆顶元素
• 四、Java中的PriorityQueue
• • 4.1 实现的接口
  • 4.2 构造方法
  • 4.3 常用方法
  • 4.4 PriorityQueue注意事项
• 五、练习

一、堆

如果有一个集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

二、堆的性质

• 堆逻辑结构上是一棵完全二叉树。
• 堆上的节点一定不大于（大根堆）或者不小于（小根堆）父亲节点。

三、大根堆的模拟实现

使用代码来实现一个大根堆。

3.1 接口实现

接口成员方法。

public class PriorityQueue {  public int[] elem; public int usedSize; public PriorityQueue() { } //建堆 public void createHeap(int[] array) { } /** * @param root 是每棵子树的根节点的下标 * @param len 是每棵子树调整结束的结束条件 * 向下调整的时间复杂度：O(logn) */ private void shiftDown(int root,int len) { } // 入堆：仍然要保持是大根堆 public void push(int val) { } private void shiftUp(int child) { } //判断堆是否满 public boolean isFull() { } //每次删除的都是优先级高的元素,删除后任是大根堆 public void pollHeap() { } //判断堆是否为空 public boolean isEmpty() { } // 获取堆顶元素 public int peekHeap() { }}

3.2 构造方法

在构造方法中构建为长度10的数组。

public PriorityQueue() {