完全二叉树与堆

完全二叉树，仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充。

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型：
1，小顶堆（min heap）：任意节点的值 小于其子节点的值。
2，大顶堆（max heap）：任意节点的值 大于其子节点的值。

编程语言提供的是优先队列（priority queue），定义为具有优先级排序的队列。堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。我们可以将“优先队列”和“堆”看作等价的数据结构。

/* 初始化堆 */// 初始化小顶堆Queue<Integer>minHeap=newPriorityQueue<>();// 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）Queue<Integer>maxHeap=newPriorityQueue<>((a,b)->b-a);/* 元素入堆 */maxHeap.offer(1);maxHeap.offer(3);maxHeap.offer(2);maxHeap.offer(5);maxHeap.offer(4);/* 获取堆顶元素 */intpeek=maxHeap.peek();// 5/* 堆顶元素出堆 */// 出堆元素会形成一个从大到小的序列peek=maxHeap.poll();// 5peek=maxHeap.poll();// 4peek=maxHeap.poll();// 3peek=maxHeap.poll();// 2peek=maxHeap.poll();// 1/* 获取堆大小 */intsize=maxHeap.size();/* 判断堆是否为空 */booleanisEmpty=maxHeap.isEmpty();/* 输入列表并建堆 */minHeap=newPriorityQueue<>(Arrays.asList(1,3,2,5,4));

堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为Ologn 。给定一组数据，我们用堆存储，然后不断地执行出堆操作，就可以得到有序数据。Top-k 是一个经典算法问题，可以使用堆数据结构高效解决 ,选择热度前 5 ，选取销量前 5 的商品等都是常见的应用。

/* 基于堆查找数组中最大的 k 个元素 */Queue<Integer>topKHeap(int[]nums,intk){// 初始化小顶堆Queue<Integer>heap=newPriorityQueue<Integer>();// 将数组的前 k 个元素入堆for(inti=0;i<k;i++){heap.offer(nums[i]);}// 从第 k+1 个元素开始，保持堆的长度为 kfor(inti=k;i<nums.length;i++){// 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆if(nums[i]>heap.peek()){heap.poll();heap.offer(nums[i]);}}returnheap;}

总共执行了 n 轮入堆和出堆，堆的最大长度为k ，因此时间复杂度为nlogk 。该方法的效率很高，当
k较小时，时间复杂度趋向n ；当 k 较大时，时间复杂度不会超过 nlogn 。