堆结构——面试算法题高频汇总

目录

引言

堆创建&增删改

堆构造过程

举个例子

堆插入元素

删除元素

在数组中找第k大的元素

举例

堆排序原理

合并k个排序链表

数据流中位数问题

---

引言

堆是将一组数据按照完全二叉树的存储顺序，将数据存储在一个一维数组中的结构。堆有两种结构，一种称为大顶堆，一种称为小顶堆。

• 小顶堆：任意节点的值均小于等于它的左右孩子，并且最小的值位于堆顶，即根节点处。

• 大顶堆：任意节点的值均大于等于它的左右孩子，并且最大的值位于堆顶，即根节点处。 有些地方也叫大根堆、小根堆，或者最大堆、最小堆都一个意思。

在Java领域，可以认为堆 就是优先级队列，反之亦然。

规律：查找：找大用小，大的进；找小用大，小的进。

排序：升序用小，降序用大。

堆创建&增删改

堆构造过程

使用数组构建堆时，就是先按照层次将所有元素依次填入二叉树中，使其成为二叉树，然后再不断调整，最终使其符合堆结构。

举个例子

比如数组是[3,1,4,5,2]，先按层排成小树：

3是树顶，下面左孩子1，右孩子4，第三层左孩子5和右孩子2。这时候树乱糟糟的，不符合堆（比如大顶堆）要求～于是从倒数第二层开始调整，先看数字1，它的左孩子5比它大，交换它们变成[3,5,4,1,2]；再往上调整树顶3，它的左孩子5比它大，交换后变成[5,3,4,1,2]，但交换后3的位置又需要和它的左孩子1比，发现没问题，调整完毕！现在整棵树像叠罗汉一样，每个爸爸都比孩子大，堆就建好啦

堆插入元素

从上面可以看到根节点和其左右子节点是堆里的老大老二和老三，其他结点则没有太明显的规律，那如果要插入一个新元素，该怎么做呢？直接说规则，将元素插入到保持其为完全二叉树的最后一个位置，然后顺着这条支路一直向上调整，每前进一层就要保证其子树都满足堆否则就去处理子树，直到完全满足要求。

删除元素

堆本身比较特殊，一般对堆中的数据进行操作都是针对堆顶的元素，即每次都从堆中获得最大值或最小值，其他的不关心，所以我们删除的时候，也是删除堆顶。

在数组中找第k大的元素

给定整数数组nums和整数k，请返回数组中第k个最大的元素。 请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

• 选择【暴力循环】

• 快排方法【之前博客有，点击查看】

• 堆查找法

关于堆查找法的思路：

找最大用小堆，找最小用大堆，找中间用两个堆

举例

序列[3,2,3,1, 2 ,4 ,5, 1,5,6,2,3]，k为4。

我们构造一个大小只有4的小根堆，堆满了之后，对于小根堆，并一定所有新来的元素都可以入堆的，只有大于根元素的才可以插入到堆中，否则就直接抛弃。这是一个很重要的前提。

元素进入的时候，先替换根元素，如果发现左右两个子树都小该怎么办呢？很显然应该与更小的那个比较，这样才能保证根元素一定是当前堆最小的。

新元素插入的时候只是替换根元素，然后重新构造成小堆，完成之后，你会神奇的发现此时根的根元素正好是第4大的元素。

这时候你会发现，不管要处理的序列有多大，或者是不是固定的，根元素每次都恰好是当前序列下的第K大元素。

由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

• 如果当前堆不满，直接添加；

• 堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

import java.util.PriorityQueue;
public class Solution {public int findKthLargest(int[] nums, int k) {if(k>nums.length){return -1;}int len = nums.length;// 使用一个含有 k 个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);for (int i = 0; i < k; i++) {minHeap.add(nums[i]);}for (int i = k; i < len; i++) {// 看一眼，不拿出，因为有可能没有必要替换Integer topEle = minHeap.peek();// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去if (nums[i] > topEle) {minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
}

堆排序原理

根节点是整个结构最大的元素，先将其拿走，剩下的重排，此时根节点就是第二大的元素，再将其拿走，再排，依次类推。

合并k个排序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

1->4->5,

1->3->4,

2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

给了数组，就建立多大的固定堆

给了几个数组，就建立多大的堆，固定大小的

public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));for (int i = 0; i < lists.length; i++) {if (lists[i] != null) {q.add(lists[i]);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while (!q.isEmpty()) {tail.next = q.poll();tail = tail.next;if (tail.next != null) {q.add(tail.next);}}return dummy.next;
}

数据流中位数问题

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如:[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。

• double findMedian() - 返回目前所有元素的中位数。

进阶问题：

1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

思路

中位数的题，一般都可以用 大顶堆 + 小顶堆来求解

小顶堆（minHeap）：存储所有元素中较大的一半，堆顶存储的是其中最小的数。

大顶堆（maxHeap）：存储所有元素中较小的一半，堆顶存储的是其中最大的数。相当于，把所有元素分成了大和小两半，而我们计算中位数，只需要大的那半的最小值和小的那半的最大值即可。

class MedianFinder {// 小顶堆存储的是比较大的元素，堆顶是其中的最小值PriorityQueue<Integer> minHeap;// 大顶堆存储的是比较小的元素，堆顶是其中的最大值PriorityQueue<Integer> maxHeap;/** initialize your data structure here. */public MedianFinder() {this.minHeap = new PriorityQueue<>();this.maxHeap = new PriorityQueue<>((a, b) -> b - a);}public void addNum(int num) {// 小顶堆存储的是比较大的元素，num比较大元素中最小的还大，所以，进入minHeapif (minHeap.isEmpty() || num > minHeap.peek()) {minHeap.offer(num);// 如果minHeap比maxHeap多2个元素，就平衡一下if (minHeap.size() - maxHeap.size() > 1) {maxHeap.offer(minHeap.poll());}} else {maxHeap.offer(num);// 这样可以保证多的那个元素肯定在minHeapif (maxHeap.size() - minHeap.size() > 0) {minHeap.offer(maxHeap.poll());}}}public double findMedian() {if( minHeap.size() > maxHeap.size() ){return minHeap.peek();}else if(minHeap.size() < maxHeap.size() ) {return maxHeap.peek();}else{return ((minHeap.peek()+maxHeap.peek())/2.0;} }
}