算法面试——堆与优先队列：前K个高频元素、合并K个链表、数据流中位数

堆（优先队列）常用于需要反复获取最大/最小值的场景。Java 中用 PriorityQueue。

一、前 K 个高频元素

publicint[]topKFrequent(int[]nums,intk){Map<Integer,Integer>freq=newHashMap<>();for(intnum:nums)freq.put(num,freq.getOrDefault(num,0)+1);// 小顶堆，保留频率最高的 k 个PriorityQueue<Integer>pq=newPriorityQueue<>((a,b)->freq.get(a)-freq.get(b));for(intkey:freq.keySet()){pq.offer(key);if(pq.size()>k)pq.poll();}int[]result=newint[k];for(inti=k-1;i>=0;i--)result[i]=pq.poll();returnresult;}

二、合并 K 个升序链表

publicListNodemergeKLists(ListNode[]lists){PriorityQueue<ListNode>pq=newPriorityQueue<>((a,b)->a.val-b.val);for(ListNodenode:lists){if(node!=null)pq.offer(node);}ListNodedummy=newListNode(0);ListNodecur=dummy;while(!pq.isEmpty()){ListNodenode=pq.poll();cur.next=node;cur=cur.next;if(node.next!=null)pq.offer(node.next);}returndummy.next;}

三、数据流中位数

classMedianFinder{privatePriorityQueue<Integer>maxHeap;// 左半部分（大顶堆）privatePriorityQueue<Integer>minHeap;// 右半部分（小顶堆）publicMedianFinder(){maxHeap=newPriorityQueue<>((a,b)->b-a);minHeap=newPriorityQueue<>();}publicvoidaddNum(intnum){if(maxHeap.isEmpty()||num<=maxHeap.peek()){maxHeap.offer(num);}else{minHeap.offer(num);}// 平衡两个堆的大小if(maxHeap.size()>minHeap.size()+1){minHeap.offer(maxHeap.poll());}elseif(minHeap.size()>maxHeap.size()){maxHeap.offer(minHeap.poll());}}publicdoublefindMedian(){if(maxHeap.size()>minHeap.size()){returnmaxHeap.peek();}return(maxHeap.peek()+minHeap.peek())/2.0;}}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/MySQL 实战干货，不让你白来。