优先级树是什么?

一、优先级树是什么

优先级树的根节点中存储的元素具有最小优先级。

优先级树是满足下面这些条件的二叉树:

1、树中的每一个节点存储一个元素；

2、任一节点中存储的元素的优先级不大于其儿子节点中元素的优先级，从根到叶子节点的任一路径上，各个节点中的元素按照优先级的非减序排列。所以根节点中存储的元素具有最小的优先级。

当一个优先级树是一个近似满二叉树时，就是称之为堆了，或者偏序树。

区别于二叉排序树（BST），优先级树通常只有偏序，即根的优先级大于左右子树，并且递归定义左右子树各自也是一颗优先级树。通常意义上讲，就是数据结构里的堆，常见实现是通过数组表示的完全二叉堆。

特性就是O(1)的堆顶查询，O(logn)的删除和插入。并且实现起来相对简单，且不存在BST的退化情况。

延伸阅读：

二、优先级队列(PriorityQueue)

优先级队列虽然也叫队列，但是和普通的队列还是有差别的。普通队列出队顺序只取决于入队顺序，而优先级队列的出队顺序总是按照元素自身的优先级。换句话说，优先级队列是一个自动排序的队列。元素自身的优先级可以根据入队时间，也可以根据其他因素来确定，因此非常灵活。

优先级队列的内部实现有很多种，例如有序数组、无序数组和堆等。但是无论哪种实现，优先级队列必须实现以下两种方法：insert和delete。insert方法是将带优先级的元素插入优先级队列中（类似队列的enQueue方法）；delete方法是从优先级队列中取出较高优先级（或最低优先级）的元素并在队列中删除该元素（类似队列的出队）。

//Go语言表示

type PriorityQueue struct {

     //隐藏实现

 }

 ​

 //以int为例，值的大小即代表元素优先级的高低（下同）

 func (pq *PriorityQueue)Insert(val int)  //插入带优先级的元素

 ​

 func (pq *PriorityQueue)Delete() int //从优先级队列中取出优先级较高的元素

针对不同实现，优先级队列的插入和删除方法的效率是不同的。