算法笔记-优先级队列-堆

优先级队列特性

• 获取最小元素提取（删除）
• 添加元素（插入）

实现方式：

• 无序链表，插入O(1), 删除时需要查找最小值O(N)
• 有序链表，插入O(N), 删除时需要查找最小值O(1)
• 二叉查找树，两种操作O(logN), 操作过多后，反复去除左子树节点会破坏平衡，加重右子树

三种实现都不理想，下面将采用非链表结构，以最坏O（logN）支持以上操作。插入花费常数时间。

二叉堆

特性

• 结构性-完全二叉树
• 堆序性- 父节点小于左右子节点

操作

• 插入
  • 上滤
• 删除最小元素
  • 下滤