[Java]快速入门优先队列(堆)手撕相关面试题
专栏简介 :java语法及数据结构
题目来源:leetcode,牛客,剑指offer
创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.
希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.
学历代表过去,能力代表现在,学习能力代表未来!
目录
前言
一>堆(heap)
1.堆的概念
2.堆的性质
3.堆的结构
编辑
二>堆的实现
1.建堆
2.建队时间复杂度分析
三>堆的应用---优先队列
模拟入队
模拟出队
模拟查看
四>topK问题
五>面试题
六>堆排序
总结
前言
优先队列(PriorityQueue)虽然在数据结构中相对较为简单,但在面试中却是常见考点,尤其是由堆排序所引申出的topK问题以及一些列算法题都不容小觑.本文由浅入深旨在带领读者对优先队列及其相关内容有深刻而广泛的认知.
一>堆(heap)
1.堆的概念
堆是将一颗完全二叉树按层序遍历的方式存入数组中.不使用非完全二叉树是因为在数组中会有空间的浪费.所以堆逻辑上是一颗完全二叉树,物理上是一个数组.满足任意节点上的值都大于其子节点的值叫大堆,反之叫小堆.
注意:对于非完全二叉树则不建议使用顺序存储,因为为了还原二叉树树,数组中必然会有空节点导致空间利用率较低,
将元素存储到数组中后则可以根据二叉树来进行还原,假设i为节点在数组中的下标.
- 如果i为0,则i表示节点为根节点,否则i节点的双亲节点为(i-1)/2.
- 如果2*i+1< 节点个数,则没有左孩子.
- 如果2*i+2< 节点个数,则没有右孩子.
2.堆的性质
- 堆中某个节点的值总是不大于或不小于父节点的值(视大小堆而定)
- 堆总是一颗完全二叉树
- 堆的作用是快速找出集合中的最值.
3.堆的结构
二>堆的实现
1.建堆
首先声明我们创建的是大根堆,建堆主要分为三步骤:
- 由于堆底层是数组,所以我们需要创建数组及其大小来初始化堆.
- 找到最后一颗子树的根节点,模拟二叉树通过不断的向下调整创建堆.
- 实现向下调整的操作也是整个操作的核心,需要注意之前得出二叉树父子节点之间的关系,循环操作即可.
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
//建大根堆
public void createHeap(int[] array) {
elem = Arrays.copyOf(array, array.length);
usedSize = array.length;
//根据代码看似时间复杂度为O(N*logn),实际为O(N)
for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
//向下调整
shifDown(parent, usedSize);
}
}
//向下调整
public void shifDown(int parent, int len) {
int child = 2 * parent + 1;
while (child < len) {
//找到孩子结点中最大值
if (child + 1 < len && elem[child] < elem[child + 1]) {
child++;
}
if (elem[child] > elem[parent]) {//交换完成
swap(elem, child, parent);
parent = child;
child = parent * 2 + 1;//像下面检索的操作,如果数组越界直接不进循环了
} else {
break;
}
}
}
//交换元素
public void swap(int[] elem, int begin, int end) {
int tmp = elem[begin];
elem[begin] = elem[end];
elem[end] = tmp;
}
2.建队时间复杂度分析
根据代码分析得出,共有n个节点所以需要遍历n次,每个节点都需要调整,所以时间复杂度应该是O(N*logn).其实不然,时间复杂度不能光看代码还要结合思想.
实际情况分析可以得出,最后一层的叶子节点不需要调整,时间复杂度为,每一层节点的个数乘以每一层的高度. 假设时间复杂度为T(n),高度为h.
T(n) = 2^0*(h-1)+2^1*(h-2)+........+2^(h-2)*1
2*T(n) = 2^1(h-1)+2^2*(h-2)+.......+2^(h-1)*1
错位相减法:
2*T(n)-T(n) = 2^0*(h-1)+2^1+2^2+......+2^(h-1)
等比数列求和:
T(n) = 2^h-1-h
深度为h的二叉树最大节点数为 2^h - 1.
n = 2^h-1
h =
T(n) = n-
当n趋近与无穷大时,
可以忽略不计.
所以时间复杂度为O(N)
三>堆的应用---优先队列
根据java的源码我们可以发现优先队列底层是小根堆.
模拟入队
- 由于优先队列底层是堆而堆的底层又是数组,所以入队需要判断数组是否满,如果满则需要扩容
- 根据堆的特性,无论是入堆还是出堆,都要保持大根堆或者小根堆.
public void offer(int val) {
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[usedSize++] = val;
shiftUp(usedSize - 1);
}
private void shiftUp(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (elem[child] > elem[parent]) {
swap(elem, child, parent);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
public boolean isFull() {
return usedSize == elem.length;
}模拟出队
- 首先判断队列是否为空,为空可以抛一个自定义异常.
- 出队需出最大的元素,所以交换0位置与usedSize-1位置的元素.数组长度- -
- 出队后,堆依旧需要保持大根堆,所以只需将0下标的元素向下调整即可.
public int poll() {
if (isEmpty()) {
throw new RuntimeException("优先级队列为空");
}
int inPoll = elem[0];
swap(elem, 0, usedSize - 1);
usedSize--;
shifDown(0, usedSize);
return inPoll;
}
public boolean isEmpty() {
return usedSize == 0;
}模拟查看
public void peek(){
if (isEmpty()){
throw new RuntimeException("优先级队列为空");
}
System.out.println(elem[0]);
}四>topK问题
给你100万个数据,让你找到前十个最大的元素.
思路一:排序最快 时间复杂度O(n*logn)
思路二:利用堆,弹出前10个元素,时间复杂度O(n*logn)
思路三:topk问题,时间复杂度O(n*logk)
总结:
- 如果要求前k个最大的元素,要建一个小根堆.(这样堆顶元素永远都是最小的元素,只需判断后续元素是否比堆顶元素大?如果比堆顶元素大就交换,否则继续比较)
- 如果要求前k个最小的元素,要建一个大根堆.
- 第K大的元素,建一个小堆,堆顶元素是第K大的元素.
- 第K小的元素,建一个大堆,堆顶元素是第K小的元素.
public class TestTopK {
//找前K个最小的元素
public static int[] topK(int[] array,int k){
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;//建大堆
}
});
for (int i = 0; i < array.length; i++) {
if (i<k){
priorityQueue.offer(array[i]);
}else {
int tmp = priorityQueue.peek();
if (tmp >array[i]){
priorityQueue.poll();
priorityQueue.offer(array[i]);
}
}
}
int[] tmp = new int[k];
for (int i = 0; i < k; i++) {
tmp[i] = priorityQueue.poll();
}
return tmp;
}
public static void main(String[] args) {
int[] array = {18,21,8,10,34,12};
int[] tmp = topK(array,3);
System.out.println(Arrays.toString(tmp));
}
}五>面试题
本题的主要思想是两个升序数组排列组合后找到前K个最大的数,属于典型的topK问题本题采用优先队列的做法.
- 首先向优先队列中传入自定义的比较器,由于是找前K个最小的数,所以自定义比较器的按降序排列,构造出大根堆.(具体原因上文中topK有介绍)
- 其次遍历两个升序数组中的元素进行排列组合,注意遍历时范围取K和数组长度的最小值,防止:(1)假如有100万个元素我们只取前3个最小的,那么如果按长度遍历明显会超时.(2)假如有5个元素但我们取前10个最小的,如果按K的大小遍历必然会越界.
- 然后判断队列是否小于K,如果小于K就向队列中存入K个元素.否则比较堆顶的元素是否大于数组中的元素,如果大于就交换.
- 最后将优先队列中元素全部弹出存入集合返回即可.
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
}
});
for (int i = 0; i < Math.min(nums1.length, k); i++) {
for (int j = 0; j < Math.min(nums2.length, k); j++) {
if (maxHeap.size() < k) {
List<Integer> tmpList = new ArrayList<>();
tmpList.add(nums1[i]);
tmpList.add(nums2[j]);
maxHeap.offer(tmpList);
} else {
int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
if (top > nums1[i] + nums2[j]) {
maxHeap.poll();
List<Integer> tmpList = new ArrayList<>();
tmpList.add(nums1[i]);
tmpList.add(nums2[j]);
maxHeap.offer(tmpList);
}
}
}
}
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
ret.add(maxHeap.poll());
}
return ret;
}六>堆排序
假设有一组数据[1,8,6,4,7,3,5,6,5],由大到小排序为[1,3,4,5,5,6,6,7,8].我们要对其进行堆排序,首选要确定使用大根堆还是小根堆?通常我们肯会认为是小根堆,但事实并非如此,如果我们按小根堆排序[1,8,6],堆顶元素一定是最小的,但左右孩子的大小并不是按它的下标来排列.但如果我们按大根堆来排列,堆顶元素一定是最大的元素,用end来记录最后一个元素的下标,通过首尾元素的互换一定能让最大的元素到末尾.以此类推当end到达堆顶时,该堆中的元素一定是按照下标从大到小排列.
public class DemoHeap {
public int usedSize;
//建大根堆
public void createHeap(int[] array) {
usedSize = array.length;
for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
//向下调整
shifDown(parent, usedSize, array);
}
}
//向下调整
public void shifDown(int parent, int len, int[] array) {
int child = 2 * parent + 1;
while (child < len) {
//找到孩子结点中最大值
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[parent]) {//交换完成
swap(array, child, parent);
// int tmp = elem[child];
// elem[child] = elem[parent];
// elem[parent] = tmp;
parent = child;
child = parent * 2 + 1;//像下面检索的操作,如果数组越界直接不进循环了
} else {
break;
}
}
}
//交换元素
public void swap(int[] array, int begin, int end) {
int tmp = array[begin];
array[begin] = array[end];
array[end] = tmp;
}
//堆排序
public void HeapSort(int[] array) {
usedSize = array.length;
int end = usedSize - 1;
while (end > 0) {
swap(array, 0, end);
shifDown(0, end, array);
end--;
usedSize--;
}
}
}
总结
以上就是优先队列(堆)的所有内容了,相信仔细阅的朋友,已经对堆及其衍生问题有了一定的了解,由于该内容在面试中属于常考题型,后续还需大量刷题来巩固提升,码字不易,如果觉得我的内容对你有帮助,记得三连哦!!
