Skip to main content

二叉堆和优先队列

· 4 min read
Zeffon Wu

二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。优先队列是计算机科学中的一类抽象数据类型。

前言​

二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。优先队列是计算机科学中的一类抽象数据类型。

正文​

Priority Queue 优先队列​

  1. 普通队列是先进先出，后进后出；优先队列的出队入队只与优先级相关
  2. 优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。
  3. 常见的场景：操作系统中任务调度（动态选择优先级最高的任务执行）
  4. 基于不同底层实现时间复杂度比较底层数据结构插入时间复杂度取出时间复杂度
    无序数组O(1)O(n)
    有序数组O(n)O(1)
    堆O(log n)O(log n)

Binary Heap 二叉堆​

  • 二叉堆是一棵完全二叉树，不会退化为链表。（二叉树在特殊情况从小到大排序是会退化成链表）

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。若设二叉树的深度为 h，除第 h 层外，其它各层 (1 ～ h-1) 的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。

  • 二叉堆中的某个节点的值总是不大于其父节点的值。若根节点是最大值则成为最大堆,反之是最小堆。
  • 二叉堆添加元素放在最后的叶子节点，再根据与其父节点的大小进行调整位置，直到满足所有的父子节点关系。
  • 二叉堆删除根节点元素，将根节点与最后的叶子节点进行互换，删除最后的叶子节点，再将根节点与其子节点进行比较互换位置，直到满足所有的父子节点关系。
  • 可以使用数组存储二叉堆。根节点为 0，按层排序下去。则父节点与其子节点的关系如下:
parent(i) = (i - 1) / 2
left child(i) = 2 * i + 1
right child(i) = 2 * i + 2

参考文献​