在上一章 《二叉树的实现(超多图、超详解)》 中,我们介绍了二叉树的存储分为: 类似于链表的链式存储和 顺序存储。链式存储在上一节介绍过了,今天将从二叉树的顺序存储过度到堆的实现。
二叉树的顺序存储:
是通过层序遍历的方式将二叉树存入数组中
注意:
顺序存储一般只使用于完全二叉树,因为非完全二叉树会造成空间浪费
由于二叉树存储在数组中,父亲节点和孩子节点的下标有以下关系:
其实二叉树的顺序存储,即将一棵完全二叉树通过层序遍历的方式存入数组中,这种方式主要的用法其实就是今天的主角堆。堆的底层就是一棵完全二叉树,并且是存储在数组中的。
堆的特类:
大根堆示例图:
小根堆示例图:
注意:
只有整个二叉树当中的每棵子树都是大堆/小堆时,整棵树才是大堆/小堆
堆的基本作用:
通过上图演示大根堆和小根堆,我们很清晰的知道,堆的最基本的作用就是:快速找到集合中的最值
步骤:
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem=new int[10];
}
}
// 创建一个大根堆
public void createHeap(int[] array){
}
// 创建一大根个堆
public void createHeap(int[] array){
// 首先把需要的数据直接存放在 elem 中,一会建堆时直接操作 elem
for(int i=0;i<array.length;i++){
this.elem[i]=array[i];
this.usedSize++;
}
}
接下来我们要解决怎么将存入的无规则的数据,转换成我们需要的大根堆的存储的顺序。
先看一个已经在 elem 中存放了数据的示例图,它的逻辑结构和物理结构如下:
接下来通过向下调整的操作,从 elem 中的最后一个值,即最后一个节点开始,找到它的父节点,再找到这个父节点的左右子树的较大的节点,如果它比父节点的值还大就进行交换。完成以后再继续向前依次进行该操作。注意: 父节点与孩子节点若交换,以孩子节点为跟节点的子树要判断是否还事一个大根堆。
我们再通过子节点如果是 i,那么父节点就是 (i-1)/2 的关系,将这棵树的子节点和父节点关联起来
实现代码:
// 创建一大根个堆
public void createHeap(int[] array){
// 首先把需要的数据直接存放在 elem 中,一会建堆时直接操作 elem
for(int i=0;i<array.length;i++){
this.elem[i]=array[i];
this.usedSize++;
}
// 从最后一个节点的父亲节点开始对其进行向下操纵
for(int parent=(this.usedSize-2)/2;parent>=0;parent--){
shiftDown(parent);
}
}
public void shiftDown(int parent){
int child=2*parent+1;
// 进入该循环说明你有左孩子,进行向下调整操作
while (child<this.usedSize){
if(child+1<this.usedSize&&this.elem[child]<this.elem[child+1]){
child++;
}
// child 所保存的下标就是左右孩子的最大值
if(this.elem[parent]<this.elem[child]){
int tmp=this.elem[parent];
this.elem[parent]=this.elem[child];
this.elem[child]=tmp;
parent=child;
child=2*parent+1;
}else {
// 该子树的向下调整操作结束
break;
}
}
}
错误计算方式(时间复杂度为:O(Nlog(N))):
O(log(N))
O(Nlog(N))
正确计算方式(时间复杂度为:O(N)):
O(N)
实际应用:
在很多应用中,我们通常需要按照优先情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象。最简单的一个例子就是,在手机上玩游戏时,如果有来电,那么系统应该优先处理进来的电话。
优先级队列:
在这种情况下,我们的数据结构应该提供两个最基本的操作:一个是返回最高优先级,另一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
思想(以大根堆为例):
实现代码:
// 判断堆是否为空
public boolean isFull(){
return this.usedSize==this.elem.length;
}
// 入堆操纵
public void push(int val){
if(isFull()){
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize++]=val;
shiftUp(this.usedSize-1);
}
// 向上调整
public void shiftUp(int child){
int parent=(child-1)/2;
while(parent>=0) {
if (this.elem[parent] < this.elem[child]) {
int tmp = this.elem[parent];
this.elem[parent] = this.elem[child];
this.elem[child] = tmp;
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
思想(以大根堆为例):
实现代码:
// 判断堆是否为空
public boolean isEmpty(){
return this.usedSize==0;
}
// 出队列
public int poll(){
if(isEmpty()){
throw new RuntimeException("队列空,不能进行出队列操作");
}
int val=this.elem[0];
this.elem[0]=this.elem[this.usedSize-1];
this.usedSize--;
// 通过向下调整
shiftDown(0);
return val;
}
思想(以大根堆为例):
直接返回堆顶元素
实现代码:
// 返回队首元素
public int peek(){
if(isEmpty()){
throw new RuntimeException("堆为空");
}
return this.elem[0];
}
TopK 问题是在一组数据当中,找到前 k 个最大的或最小的数据。
示例:
如我们有一百个数据,我们要得到前十个最大或最小的元素
处理 TopK 问题的方法有很多,如:简单的排序、堆、分治法、减治法等等。
今天将用堆来处理这个 TopK 问题
下面思路以找到前 k 个最大的元素为例,如果是找前 k 个最小的几个元素,则做法相反
O(N*log(N))
O(N*log(k))
下面代码以找到前 k 个最大的元素为例,如果是找前 k 个最小的几个元素,则做法相反
// 找到前 k 个最大的元素
public static int[] topK(int[] array, int k){
// 默认建小堆
PriorityQueue<Integer> minHeap=new PriorityQueue<>();
for(int i=0;i<array.length;i++){
if(i<k){
minHeap.offer(array[i]);
}else {
if (array[i] > minHeap.peek()) {
minHeap.poll();
minHeap.offer(array[i]);
}
}
}
int[] elem=new int[k];
for(int i=k-1;i>=0;i--){
elem[i]=minHeap.poll();
}
return elem;
}
思路:
如果我们要使用堆去对一些数据进行排序,那么我们该怎么做呢?
这里以从小到大排序为例,如果要从大到小的话以下思路就是反的
首先我们明确是建一个大根堆,然后堆顶元素就是最大的,然后我们将堆顶元素与堆尾元素交换,此时最后一个元素就是最大的元素,然后通过向上调整,保证堆顶元素为最大的,然后与堆的倒数第二个元素进行交换,这样我们就可以在每次交换中使从最末尾的元素开始依次变小的排序。
这里以从小到大排序为例,如果要从大到小的话以下思路就是反的
public static void heapSort(int[] array){
// 下面将默认的大堆改成小堆,并且使用了匿名内部类的方式
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(int i=0;i<array.length;i++){
maxHeap.offer(array[i]);
}
int end=array.length-1;
while(end>=0){
int val=maxHeap.poll();
array[end]=val;
end--;
}
}
题目(OJ 链接):
给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
代码:
class Solution {
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(k,nums1.length);i++){
for(int j=0;j<Math.min(k,nums2.length);j++){
List<Integer> list=new ArrayList<>();
if(maxHeap.size()<k){
list.add(nums1[i]);
list.add(nums2[j]);
maxHeap.offer(list);
}else{
int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);
if((nums1[i]+nums2[j])<top){
maxHeap.poll();
list.add(nums1[i]);
list.add(nums2[j]);
maxHeap.offer(list);
}
}
}
}
List<List<Integer>> minKList=new ArrayList<>();
for(int i=0;i<k && !maxHeap.isEmpty();i++){
minKList.add(maxHeap.poll());
}
return minKList;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_51367845/article/details/121181717
内容来源于网络,如有侵权,请联系作者删除!