我理解的数据结构（七）——堆和优先队列（HeapAndPriorityQueue）一、堆1、堆的基本也是树堆最主流的实现：二叉堆二叉堆是一棵完全二叉树2.完全二叉树完全二叉树是一种非常高效的数据结构，完全二叉树是由一棵完全二叉树衍生而来的。对于一棵深度为K，有n个节点的二叉树，当且仅当每个节点与深度为K的满二叉树中编号为1到n的节点之间存在一一对应关系时，称为完全二叉树的K。（通俗地说：完全二叉树不一定是满二叉树，当一层满了不能容纳新节点时，新层会从左到右包含新节点，缺失的节点一定在右边）最大堆：堆中某个节点的值永远不大于其父节点的值（对应的，可以定义最小堆）3.使用数组存储二叉堆4.基本代码实现这里ArrayNew是我之前实现的数组：ArraycodepublicclassHeap>{privateArrayNewdata;publicHeap(intcapacity){data=newArrayNew<>(capacity);}publicHeap(){data=newArrayNew<>();}//返回堆中元素的个数publicintsize(){returndata.getSize();}//堆是否包含元素publicbooleanisEmpty(){returndata.isEmpty();}//父节点privateintparent(intindex){if(index==0){thrownewIllegalArgumentException("index-0doesn'thaveparent");}返回（索引-1）/2;}//左子节点索引privateintleftChild(intindex){return2*index+1;}//右子节点索引privateintrightChild(intindex){return2*index+2;}}5.添加元素（筛选）步骤：在最后一层末尾添加这个元素。如果树已满，则将其添加到新层的最左端，以便与其父节点进行比较。如果父节点比当前元素的节点小，位置被替换等等，直到比较到根节点//添加元素publicvoidadd(Ee){data.addLast(e);siftUp(data.getSize()-1);}//FloatingprivatevoidsiftUp(intindex){//添加的元素大于父节点的元素while(index>0&&data.get(index).compareTo(data.get(parent(index)))>0){data.swap(index,parent(index));索引=父（索引）；}}6.取出元素（siltdown）步骤：最后一个节点和根节点交换，取出最后一个节点，这样整体的树结构不会改变，但是不会和元素比较位置根节点和子节点。如果小于子节点的最大节点元素，则进行位置替换，以此类推，直到大于子节点的元素。//检查堆中的最大值publicEfindMax(){if(data.isEmpty()){thrownewIllegalArgumentException("can'tfindMaxinemptyheap");}returndata.get(0);}//获取堆中的最大值publicEextractMax(){Eret=data.get(0);data.swap(0,data.getSize()-1);数据.removeLast();筛选（0）；returnret;}//SinkprivatevoidsiftDown(intindex){while(leftChild(index)0){j=j+1;}//此时data[j]为左右子节点的最大节点值if(data.get(j).compareTo(data.get(index))<=0){break;}data.swap(index,j);指数=j;}}7.Heapify和replacereplace（取出堆中最大的元素，然后放一个新元素）实现：可以先extractMax再add，但是这样会有两次O(logn)的操作优化：可以替换top堆的元素然后siftDown，所以只有一个O(logn)操作//取出堆中最大的元素，替换为元素e，重新siftDownpublicEreplace(Ee){Eret=data.get(0);数据集（0，e）；筛选（0）；returnret;}heapify（将任意数组排列成堆的形状）实现：将n个元素一个一个插入到一个空堆中，算法复杂度为O(logn)优化：heapify（算法复杂度为O(n)）将任意一个数组都可以看成一棵完全二叉树（虽然元素位置错了），找到最后一个非叶子节点（最后一个节点的父节点），从最后一个非叶子节点开始，连续siftDown每个节点//heapifypublicHeap(E[]arr){data=newArrayNew<>(arr);对于(inti=parent(data.getSize()-1);i>0;i--){siftDown(i);}}8。复杂度分析因为取出和加入堆的复杂度是O(logn)，所以堆的性能很高操作时间复杂度addO(logn)extractMaxO(logn)2.优先级队列1.优先级队列基本普通队列：先进先出，后进后出InterfacepublicinterfaceQueue{intgetSize();布尔isEmpty();无效排队（Ee）；E出列();//查看头部元素EgetFront();}3.基于堆的优先队列代码ImplementpublicclasspriorityQueue>implementsQueue{Heapdata;publicpriorityQueue(){data=newHeap<>();}@OverridepublicintgetSize(){返回数据。尺寸（）;}@OverridepublicbooleanisEmpty(){returndata.isEmpty();}@Overridepublicvoidenqueue(Ee){data.add(e);}@OverridepublicEdequeue(){返回数据。最大提取物（）；}@OverridepublicEgetFront(){returndata.findMax();}}4。LeetCode中关于优先级队列的问题347.TopK高频元素Topic:347.TopK高频元素描述：给定一个非空整数数组，返回出现频率最高的前k个元素。示例：示例1：输入：nums=[1,1,1,2,2,3],k=2输出：[1,2]示例2：输入：nums=[1],k=1输出：[1]解决方案代码：importjava.util.ArrayList;importjava.util.List;importjava.util.TreeMap;//只需要在`Solution`类中引入需要的类//所有的类都可以在上一篇博客publicclassSolution{privateclassFreqimplementsComparable{publicinte,freq;publicFreq(inte,intfreq){this.e=e;this.freq=频率；}@OverridepublicintcompareTo(Freqanother){if(this.freqanother.freq){return-1;}否则{返回0;}}}publicListtopKFrequent(int[]nums,intk){TreeMapmap=newTreeMap<>();for(intnum:nums){if(map.containsKey(num)){地图。put(num,map.get(num)+1);}else{map.put(num,1);}}PriorityQueuepq=newPriorityQueue<>();for(intkey:map.keySet()){if(pq.getSize()pq.getFront().freq){pq.dequeue();pq.enqueue(newFreq(key,map.get(key)));}}ArrayListlist=newArrayList<>();while(!pq.isEmpty()){list.add(pq.dequeue().e);}返回列表；}}
