文章目录

1. priority queue
   1. binary heap
   2. d-堆

priority queue

binary heap

堆是一棵完全填满的二叉树，，这样的树称为完全二叉树

数组实现：

• 对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元（2i+1），父亲在 i/2上

使操作快速执行的性质是堆序性（heap order）
在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或者等于）X中的关键字。

基本操作

• insert
• deleteMin

O(log N)

d-堆