1 定义如下：首先堆树是一个完全二叉树 其次堆中的某个节点总是大于或者小于其孩子节点的值 最后堆树中每个节点的子树都是堆树
补充：
完全二叉树(Complete Binary Tree)： 每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。
完美二叉树(Perfect Binary Tree) 所有的非叶子结点都有两个孩子，所有的叶子结点都在同一层。
2 最大堆 最小堆
3 堆树的操作
原始数据采用顺序存储方式
最大堆的构造：待学习
树的节点个数是n，以1为下标开始编号，直到n结束，对于节点I,其父节点为i/2，左孩子为i*2,右孩子节点为i*2+1；最后一个节点为N,其父节点为n/2
用priorityQueue（优先队列），一个基于优先级堆的无界优先队列。最大堆和最小堆实际上是一个堆，不指定comparator时默认最小堆，通过传入自定义的Comparator函数可以实现大顶堆
PriorityQueue minHeap = new PriorityQueue(); //小顶堆，默认容量为11
PriorityQueue maxHeap = new PriorityQueue(11,new Comparator(){ //大顶堆，容量11
@Override
public int compare(Integer i1,Integer i2){
return i2-i1;
}
});
常见操作：
poll(),offer(Object),size(),peek()等。
插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ；
remove(Object) 和 contains(Object) 时间复杂度为O(n)；
检索方法（peek、element 和 size）时间复杂度为常量。
API文档说明：
构造方法摘要PriorityQueue()
方法摘要 add()指定元素插入到此优先队列中 remove()移除指定元素clear()移除所有元素 offer()插入元素到队列 peek()和poll()前者获取 后者获取并且移除
解决TOP k 问题
优先队列是不同于先进先出队列的另外一种队列。每次从队列中取出的都是具有最高优先权的元素。默认自然顺序排列，也可以根据Comparator来指定
优先队列不允许NULL元素，不允许插入不可比较的对象
用add一个个加上去，自动给你排好序
注意1 该队列是用数组实现的，但是数组的大小可以动态增加，容量无限
注意2 此实现是不同步的
注意3 不允许使用null元素
注意4 插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ；
remove(Object) 和 contains(Object) 时间复杂度为O(n)；
检索方法（peek、element 和 size）时间复杂度为常量。
排序的主要有两种：快速排序和基于堆实现的优先级队列 求Top K 更简单的方法可以直接使用内置的Treemap或者treeset 这两者都是基于红黑树的一种数据结构
，每次添加新元素，其排序的开销都要大于对调整的开销，堆化
网友评论